关于有向图的连通问题

有n个顶点的有向图，至少需要多少条弧才能保证是连通的。我看了有个学长写的答案是n，我觉得n不可能正确。我的想法是要保证连通，得是n-1个点构成一个有向图的强连通图，那么弧数就是(n-1)*(n-2) 再将剩下的那个节点与这个强连通图相连，那么问题来了，这个时候是该加一条有向弧，还是该加两条有向弧呢？

Java图的强连通分量与最短路径

如何实现 下面两个类中的强连通分量(SCC)与最短路径（shortestPath) ``` package graphs; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; public class AdjacencyListGraph<T> extends Graph<T> { Map<T, Vertex> keyToVertex; private class Vertex { T key; List<Vertex> successors; List<Vertex> predecessors; Vertex(T key) { this.key = key; this.successors = new ArrayList<Vertex>(); this.predecessors = new ArrayList<Vertex>(); } } AdjacencyListGraph(Set<T> keys) { this.keyToVertex = new HashMap<T, Vertex>(); for (T key : keys) { Vertex v = new Vertex(key); this.keyToVertex.put(key, v); } } @Override public int size() { return this.keyToVertex.size(); } @Override public int numEdges() { int count = 0; for (Vertex v : this.keyToVertex.values()) { count += v.successors.size(); } return count; } @Override public boolean addEdge(T from, T to) { if (!this.keyToVertex.containsKey(from)) { throw new NoSuchElementException("Could not find vertex with key " + from.toString()); } if (!this.keyToVertex.containsKey(to)) { throw new NoSuchElementException("Could not find vertex with key " + to.toString()); } Vertex fromV = this.keyToVertex.get(from); Vertex toV = this.keyToVertex.get(to); List<Vertex> fromSuccs = fromV.successors; List<Vertex> toPreds = toV.predecessors; if (fromSuccs.contains(toV)) { return false; } fromSuccs.add(toV); toPreds.add(fromV); return true; } @Override public boolean hasVertex(T key) { return this.keyToVertex.containsKey(key); } @Override public boolean hasEdge(T from, T to) throws NoSuchElementException { if (!this.keyToVertex.containsKey(from)) { throw new NoSuchElementException("Could not find vertex with key " + from.toString()); } if (!this.keyToVertex.containsKey(to)) { throw new NoSuchElementException("Could not find vertex with key " + to.toString()); } Vertex fromV = this.keyToVertex.get(from); Vertex toV = this.keyToVertex.get(to); List<Vertex> fromSuccs = fromV.successors; List<Vertex> toPreds = toV.predecessors; if (fromSuccs.contains(toV)) { return true; } return false; } @Override public boolean removeEdge(T from, T to) throws NoSuchElementException { if (!this.keyToVertex.containsKey(from)) { throw new NoSuchElementException("Could not find vertex with key " + from.toString()); } if (!this.keyToVertex.containsKey(to)) { throw new NoSuchElementException("Could not find vertex with key " + to.toString()); } Vertex fromV = this.keyToVertex.get(from); Vertex toV = this.keyToVertex.get(to); if (!this.hasEdge(from, to)) { return false; } List<Vertex> fromSuccs = fromV.successors; List<Vertex> toPreds = toV.predecessors; fromSuccs.remove(toV); toPreds.remove(fromV); if (!fromSuccs.contains(toV)) { return true; } return false; } @Override public int outDegree(T key) { return this.keyToVertex.get(key).successors.size(); } @Override public int inDegree(T key) { return this.keyToVertex.get(key).predecessors.size(); } @Override public Set<T> vertexSet() { Set<T> vertexSet = new HashSet<T>(); for (T v : this.keyToVertex.keySet()) { vertexSet.add(v); } return vertexSet; } @Override public List<T> successorList(T key) { List<T> successorList = new ArrayList<T>(); for (Vertex v : this.keyToVertex.get(key).successors) { successorList.add(v.key); } return successorList; } @Override public List<T> predecessorList(T key) { List<T> predecessorList = new ArrayList<T>(); for (Vertex v : this.keyToVertex.get(key).predecessors) { predecessorList.add(v.key); } return predecessorList; } @Override public Iterator<T> successorIterator(T key) { return new theIterator(this.successorList(key)); } @Override public Iterator<T> predecessorIterator(T key) { return new theIterator(this.predecessorList(key)); } private class theIterator implements Iterator<T> { List<T> target; int index = 0; public theIterator(List<T> theList) { this.target = theList; } @Override public boolean hasNext() { return this.index < this.target.size(); } @Override public T next() { if (hasNext()) { this.index += 1; return this.target.get(this.index - 1); } return null; } } @Override public Set<T> stronglyConnectedComponent(T key) { this.keyToVertex.get(key); // TODO return null; } @Override public List<T> shortestPath(T startLabel, T endLabel) { // TODO return null; } } ``` 以及 ``` package graphs; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.Iterator; import java.util.List; import java.util.Map; import java.util.NoSuchElementException; import java.util.Set; public class AdjacencyMatrixGraph<T> extends Graph<T> { Map<T, Integer> keyToIndex; List<T> indexToKey; int[][] matrix; AdjacencyMatrixGraph(Set<T> keys) { int size = keys.size(); this.keyToIndex = new HashMap<T, Integer>(); this.indexToKey = new ArrayList<T>(); this.matrix = new int[size][size]; // need to populate keyToIndex and indexToKey with info from keys for (T each : keys) { this.indexToKey.add(each); } for (int i = 0; i < size; i++) { this.keyToIndex.put(this.indexToKey.get(i), i); } } @Override public int size() { return this.keyToIndex.size(); } @Override public int numEdges() { int count = 0; for (int i = 0; i < this.matrix.length; i++) { for (int j = 0; j < this.matrix[i].length; j++) { count += this.matrix[i][j]; } } return count; } @Override public boolean addEdge(T from, T to) { if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) { throw new NoSuchElementException(); } int iFrom = this.keyToIndex.get(from); int iTo = this.keyToIndex.get(to); if (this.matrix[iFrom][iTo] == 1) { return false; } this.matrix[iFrom][iTo] = 1; return true; } @Override public boolean hasVertex(T key) { return this.keyToIndex.containsKey(key); } @Override public boolean hasEdge(T from, T to) throws NoSuchElementException { if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) { throw new NoSuchElementException(); } int iFrom = this.keyToIndex.get(from); int iTo = this.keyToIndex.get(to); return this.matrix[iFrom][iTo] == 1; } @Override public boolean removeEdge(T from, T to) throws NoSuchElementException { if (!this.keyToIndex.containsKey(from) || !this.keyToIndex.containsKey(to)) { throw new NoSuchElementException(); } int iFrom = this.keyToIndex.get(from); int iTo = this.keyToIndex.get(to); if (this.matrix[iFrom][iTo] == 0) { return false; } this.matrix[iFrom][iTo] = 0; return true; } @Override public int outDegree(T key) { int iFrom = this.keyToIndex.get(key); int l = this.matrix[iFrom].length; int out = 0; for (int i = 0; i < l; i++) { out += this.matrix[iFrom][i]; } return out; } @Override public int inDegree(T key) { int iTo = this.keyToIndex.get(key); int l = this.matrix.length; int in = 0; for (int i = 0; i < l; i++) { in += this.matrix[i][iTo]; } return in; } @Override public Set<T> vertexSet() { Set<T> vertexSet = new HashSet<T>(); for (T v : this.indexToKey) { vertexSet.add(v); } return vertexSet; } @Override public List<T> successorList(T key) { int iFrom = this.keyToIndex.get(key); List<T> successorList = new ArrayList<T>(); for (int i = 0; i < this.matrix[iFrom].length; i++) { if (this.matrix[iFrom][i] == 1) { successorList.add(this.indexToKey.get(i)); } } return successorList; } @Override public List<T> predecessorList(T key) { int iTo = this.keyToIndex.get(key); List<T> predecessorList = new ArrayList<T>(); for (int i = 0; i < this.matrix.length; i++) { if (this.matrix[i][iTo] == 1) { predecessorList.add(this.indexToKey.get(i)); } } return predecessorList; } @Override public Iterator<T> successorIterator(T key) { return new successorIterator(this.keyToIndex.get(key)); } private class successorIterator implements Iterator<T> { int iFrom; int index = 0; public successorIterator(int iFrom) { this.iFrom = iFrom; } @Override public boolean hasNext() { while (true) { if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iFrom].length) { return false; } if (AdjacencyMatrixGraph.this.matrix[this.iFrom][this.index] == 1) { return true; } this.index++; } } @Override public T next() { if (hasNext()) { this.index++; return AdjacencyMatrixGraph.this.indexToKey.get(this.index - 1); } return null; } } @Override public Iterator<T> predecessorIterator(T key) { return new predecessorIterator(this.keyToIndex.get(key)); } private class predecessorIterator implements Iterator<T> { int iTo; int index = 0; public predecessorIterator(int iTo) { this.iTo = iTo; } @Override public boolean hasNext() { while (true) { if (this.index >= AdjacencyMatrixGraph.this.matrix[this.iTo].length) { return false; } if (AdjacencyMatrixGraph.this.matrix[this.index][this.iTo] == 1) { return true; } this.index++; } } @Override public T next() { if (hasNext()) { this.index += 1; return AdjacencyMatrixGraph.this.indexToKey.get(this.index); } return null; } } boolean[] visited = new boolean[this.size()]; @Override public Set<T> stronglyConnectedComponent(T key) { // TODO return null; } @Override public List<T> shortestPath(T startLabel, T endLabel) { // TODO return null; } } ```

强连通图 的 缩点 逆图 什么意思

强连通分量中，缩点什么意思。 Kosaraju算法的逆图什么意思。

强连通分量

Description Once upon a time there lived a king and he had N sons. And there were N beautiful girls in the kingdom and the king knew about each of his sons which of those girls he did like. The sons of the king were young and light-headed, so it was possible for one son to like several girls. So the king asked his wizard to find for each of his sons the girl he liked, so that he could marry her. And the king's wizard did it -- for each son the girl that he could marry was chosen, so that he liked this girl and, of course, each beautiful girl had to marry only one of the king's sons. However, the king looked at the list and said: "I like the list you have made, but I am not completely satisfied. For each son I would like to know all the girls that he can marry. Of course, after he marries any of those girls, for each other son you must still be able to choose the girl he likes to marry." The problem the king wanted the wizard to solve had become too hard for him. You must save wizard's head by solving this problem. Input The first line of the input contains N -- the number of king's sons (1 <= N <= 2000). Next N lines for each of king's sons contain the list of the girls he likes: first Ki -- the number of those girls, and then Ki different integer numbers, ranging from 1 to N denoting the girls. The sum of all Ki does not exceed 200000. The last line of the case contains the original list the wizard had made -- N different integer numbers: for each son the number of the girl he would marry in compliance with this list. It is guaranteed that the list is correct, that is, each son likes the girl he must marry according to this list. Output Output N lines.For each king's son first print Li -- the number of different girls he likes and can marry so that after his marriage it is possible to marry each of the other king's sons. After that print Li different integer numbers denoting those girls, in ascending order. Sample Input 4 2 1 2 2 1 2 2 2 3 2 3 4 1 2 3 4 Sample Output 2 1 2 2 1 2 1 3 1 4

求强连通分量入门题hdu1269迷宫城堡wa掉了大神帮忙看看

迷宫城堡 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 17155 Accepted Submission(s): 7507 Problem Description 为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。 Input 输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。 Output 对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。 Sample Input 3 3 1 2 2 3 3 1 3 3 1 2 2 3 3 2 0 0 Sample Output Yes No 下面是我写了 注释是我自己理解的不知道对不对 求指点！ import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Main { private static int n; private static int m; private static int[] dfn; private static int[] low; private static int time; private static Stack<Integer> stack; private static int sum; private static ArrayList[] list; public static void main(String[] args) { // TODO 自动生成的方法存根 Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { scn(scanner);//输入 bud(); //算法 out(); //输出 } } private static void out() { // TODO 自动生成的方法存根 if (sum==1) { System.out.println("Yes"); }else { System.out.println("No"); } } private static void bud() { dfn = new int [n+1];//次序数组 low = new int [n+1];//记录此点所能到达最早栈中的值 time = 0;//时间戳 sum = 0;//记录此图有几个强连通分量 stack = new Stack<Integer>(); //强连通分量一定是个环 此栈相当于这个环中的任意一条弧 Targan_bfs(1); } private static void Targan_bfs(int i) { dfn[i] = low[i] = ++time;//low先初始跟次序相同 stack.push(i);//将点i压入栈 //之后进行bfs搜索 枚举每一种成环的可能 for (int j = 0; j <list[i].size() ; j++) { int k= (int) list[i].get(j); if(dfn[k]==0){ Targan_bfs(k); low[i] = Math.min(low[i], low[k]); //如果进行了递归存在下一个连通点并且这点不在栈里 //那么根据low的定义 low = min{low[i],low[k]} }else { low[i] = Math.min(low[i], dfn[k]); //不进行递归那么表示下一个连通点在栈中 //根据low的的定义 low = min{low[i],dnf[k]} } } if (low[i]==dfn[i]) { //当low[i]=dfn[i]表示他自身构成了环 所以他是一个独立的连通分量 sum ++;int k = 0; //为什么循环出栈呢 //如果所有的点都相互连通那么在最后搜到的点low【最后】=low【首先】 //同理 每当你找到一个强连通分量那么请都弹出去 do { k = stack.pop(); } while (low[k]!=dfn[k]&&!stack.isEmpty()); } } private static void scn(Scanner scanner) { n = scanner.nextInt(); m = scanner.nextInt(); if(n==0&&m==0){java.lang.System.exit(0);} list = new ArrayList[n+1]; for(int i=0;i<=n;i++){list[i]=new ArrayList<Integer>();} for (int i = 0; i <m; i++) { int a = scanner.nextInt(); int b = scanner.nextInt(); list[a].add(b); } } }

数据结构的问题 在线等！！！

完成图的深度优先遍历，并基于深度优先遍历，求： a. 无向图图的连通分量 b. 检测图是否有环 c. 有向图的强连通分量

有算法能够遍历无向图中所有连通顶点的组合的算法么

有算法能够遍历无向连通图中所有子连通图的算法么

如何用邻接矩阵判断无向图的连通性？

如何用邻接矩阵判断无向图的连通性？ 要Java或者C#的实现思路，最好有代码。

matlab划分成几个互不连通的子图

背景：连通性分析，判断当前邻接矩阵W可以划分成几个互不联通的子图 如果图可以划分成2个互不联通的子图，那么其邻接矩阵W通过行列交换变换以后应该可以划分为[A,0;0,B]这种形式,其两个互不联通的子图的邻接矩阵为A，B 类似的，划分成2个互不联通的子图，其邻接矩阵通过行列交换变换以后应为[A,0,0;0,B,0;0,0,C]的形式，其三个互不联通的子图的邻接矩阵为A，B，C -->求大佬们帮助的问题是，给出一个邻接矩阵W，我想知道其可以划分为几个互不联通的子图？划分出来的子图的邻接矩阵分别是什么?

C语言的数据结构的连通图的问题，用C语言怎么编写代码去实现？

Problem Description 众所周知，度度熊喜欢图，尤其是联通的图。 今天，它在图上又玩出了新花样，新高度。有一张无重边的无向图， 求有多少个边集，使得删掉边集里的边后，图里恰好有K个连通块。 Input 第一行为T，表示输入数据组数。 对于每组数据，第一行三个整数N,M,K，表示N个点M条边的图。 接下来M行每行两个整数a,b，表示点a和点b之间有一条边。 1≤T≤20 1≤K≤N≤14 0≤M≤N∗(N+1)/2 1≤a,b≤N Output 对第i组数据，输出 Case #i: 然后输出一行，仅包含一个整数，表示方法种数（对 1 000 000 009 取模） 。 Sample Input 3 1 0 1 1 1 1 1 1 3 3 2 1 2 2 3 1 3 Sample Output Case #1: 1 Case #2: 2 Case #3: 3

用邻接表作无向连通图的存储结构写一算法

用邻接表作无向连通图的存储结构，请写一算法，求图中一条包含所有項点的简单路径，并依次输出路径中所有结点的编号

广度优先搜索树 非连通图的遍历

在数据结构教程里，有一章是实现广度优先遍历非联通图，然后把遍历的图的节点 存在树的结构里，树的储存方式是孩子兄弟表示法。当我运行代码后，输入 了图的节点和节点之间的关系： 13,13 1 2 3 4 5 6 7 8 9 10 11 12 13 1,2 1,3 1,6 1,12 2,13 4,5 7,8 7,10 7,9 8,10 11,12 11,13 12,13 该有的结果应该是： 1 2 13 3 6 12 11 4 5 7 8 9 10 可我运行的结果是123 \n 456，也就是说function BFSForest根本没有被执行。 哪位大神可以帮我看看问题出在哪，谢谢！ 以下是我的代码。 ``` #include <stdio.h> #include <stdlib.h> #define MAX_VER_NUM 20 //图的最大节点数 #define VRTYPE int //弧的类型 #define VertexType int //节点类型 typedef enum {false,true} bool; bool visited[MAX_VER_NUM]; typedef struct { VRTYPE adj; }adjMatrix[MAX_VER_NUM][MAX_VER_NUM];//图的邻接矩阵 typedef struct { VertexType ver[MAX_VER_NUM]; adjMatrix arcs; int num_vex,num_arcs; }MGraph;//图的结构体 typedef struct { VertexType data; struct gNode* lchild; struct gNode* nextsibling; }gNode;//生成树的节点，用孩子兄弟表示法 typedef struct { struct QueueCell *next; gNode *node; }QueueCell;//队列的节点 typedef struct { QueueCell *top; QueueCell *tail; }Queue;//定义队列的结构体 void initQueue(Queue **q) { if(!*q) { *q=(Queue*)malloc(sizeof(Queue)); (*q)->top=(QueueCell*)malloc(sizeof(QueueCell)); (*q)->top->next=NULL; (*q)->top->node=NULL; (*q)->tail=(*q)->top;//空队列头和尾巴在一起 } } int isEmpty(Queue *q) { if(q->tail==q->top)//空队列头和尾巴在一起 { return 1; } return 0;//如果判定结果为错，必须返回0，而不能是-1 } void EnQueue(Queue **q,gNode *g) { if(isEmpty(*q))//当队列为空时，头指针的next指针指向进队的节点 { QueueCell *c=(*q)->top->next; c->node=g; (*q)->tail=c; } else//如果队列不为空，头指针不变，更新尾巴 { QueueCell *c=(*q)->tail->next; c->node=g; (*q)->tail=c; } } gNode* DeQueue(Queue **q) { QueueCell *c=(*q)->top->next; (*q)->top->next= c->next; if(!(c->next))//出队后，队列为空时，尾巴重新指向头结点 { (*q)->tail=(*q)->top; } return c->node; } int locateVex(MGraph *G,VertexType v) { for(int i=0;i<G->num_vex;i++) { if(G->ver[i]==v) { return i; } } return -1; } void createGraph(MGraph *G) { scanf("%d,%d",&(G->num_vex),&(G->num_arcs));//输入图的节点数和弧的数量 for(int i=0;i<G->num_vex;i++) { scanf("%d",&(G->ver[i]));//输入图每个节点的值 } for(int i=0;i<G->num_vex;i++)//初始化邻接矩阵 { for(int j=0;j<G->num_vex;j++) { G->arcs[i][j].adj=0; } } for(int i=0;i<G->num_arcs;i++)//更新邻接矩阵 { VertexType v1,v2; scanf("%d,%d",&v1,&v2); int n1=locateVex(G,v1); int n2=locateVex(G,v2); if(n1==-1||n2==-1) { printf("no such vertex"); exit(-1); } G->arcs[n1][n2].adj=1; G->arcs[n2][n1].adj=1; } } int firstAdjVex(MGraph *G,int v)//找到指定节点第一个相邻节点 { for(int i=0;i<G->num_vex;i++) { if(G->arcs[v][i].adj) { return i; } } return -1; } int nextAdjVex(MGraph *G, int v,int w)//找到指定节点下一个相邻节点 { for(int i=w+1;i<G->num_vex;i++) { if(G->arcs[v][i].adj) { return i; }dang } return -1; } void visit(gNode *g) { printf("%d ",g->data); } void BFSTree(MGraph *G,gNode **g) { printf("BFSTree"); gNode *node=NULL; Queue *q=NULL; initQueue(&q); EnQueue(&q,*g); int p=locateVex(G,(*g)->data); visited[p]=true; while(!isEmpty(q)) { bool first =true; gNode* n=DeQueue(&q); node=n; int v=locateVex(G,node->data); for(int i=firstAdjVex(G,v);i>=0;i=nextAdjVex(G,v,i)) { if(!visited[i]) { gNode *gnode=(gNode*)malloc(sizeof(gNode)); gnode->data=G->ver[i]; gnode->lchild=NULL; gnode->nextsibling=NULL; visited[i]=true; EnQueue(&q,gnode); if(first) { node->lchild=gnode; first=false; } else { node->nextsibling=gnode; } node=gnode; } } } } void BFSForest(MGraph *G,gNode **g) { (*g)=NULL; for(int i=0;i<G->num_vex;i++) { visited[i]=false; }dang gNode *node=NULL; int v = locateVex(G,(*g)->data); visited[v]=true; for(int i=0;i<G->num_vex;i++) { if(!visited[i]) { gNode *n=(gNode*)malloc(sizeof(gNode)); n->data=G->ver[i]; n->lchild=NULL; n->nextsibling=NULL; if(!(*g)) { *g=n; } else { node->nextsibling=n;dang } node=n; BFSTree(G,&n); } } } void preOrderTraverse(gNode *g) { visit(g); preOrderTraverse(g->lchild); preOrderTraverse(g->nextsibling); } int main(void) { MGraph G; createGraph(&G); printf("123\n"); gNode *g; printf("456\n"); BFSForest(&G,&g); printf("789\n"); preOrderTraverse(g); return 0; } ```

给一个图G的邻接矩阵，请你判断是否连通。用语言表示出来？

给一个图G的邻接矩阵，请你判断是否连通。用语言表示。请问用深度优先遍历的话怎么描述出来呢？麻烦大佬了谢谢

K个联通块

Problem Description 众所周知，度度熊喜欢图，尤其是联通的图。 今天，它在图上又玩出了新花样，新高度。有一张无重边的无向图， 求有多少个边集，使得删掉边集里的边后，图里恰好有K个连通块。 Input 第一行为T，表示输入数据组数。 对于每组数据，第一行三个整数N,M,K，表示N个点M条边的图。 接下来M行每行两个整数a,b，表示点a和点b之间有一条边。 1≤T≤20 1≤K≤N≤14 0≤M≤N∗(N+1)/2 1≤a,b≤N Output 对第i组数据，输出 Case #i: 然后输出一行，仅包含一个整数，表示方法种数（对 1 000 000 009 取模） 。 Sample Input 3 1 0 1 1 1 1 1 1 3 3 2 1 2 2 3 1 3 Sample Output Case #1: 1 Case #2: 2 Case #3: 3

利用C程序编写的语言，求有多少个边集，使得删掉边集里的边后，图里恰好有K个连通块

Problem Description 众所周知，度度熊喜欢图，尤其是联通的图。 今天，它在图上又玩出了新花样，新高度。有一张无重边的无向图， 求有多少个边集，使得删掉边集里的边后，图里恰好有K个连通块。 Input 第一行为T，表示输入数据组数。 对于每组数据，第一行三个整数N,M,K，表示N个点M条边的图。 接下来M行每行两个整数a,b，表示点a和点b之间有一条边。 1≤T≤20 1≤K≤N≤14 0≤M≤N∗(N+1)/2 1≤a,b≤N Output 对第i组数据，输出 Case #i: 然后输出一行，仅包含一个整数，表示方法种数（对 1 000 000 009 取模） 。 Sample Input 3 1 0 1 1 1 1 1 1 3 3 2 1 2 2 3 1 3 Sample Output Case #1: 1 Case #2: 2 Case #3: 3

python networkx 有没有函数可以实现 判断一个无向图中两个结点是否连通

python networkx 有没有函数可以实现 判断一个无向图中两个结点是否连通

求一个算法，求无向连通图的两点之间最近距离，设权值都为1，考试急用，谢谢大神

求一个算法，求无向连通图的两点之间最近距离，设权值都为1，考试急用，谢谢大神

opencv　提取一个连通区域内的颜色

opencv　提取一个连通区域内的颜色，是不是通过提取连通分量就可以了,例如一个装菜的碟子，提取碟子的颜色;图像形态学了解比较少，多谢

终于明白阿里百度这样的大公司，为什么面试经常拿ThreadLocal考验求职者了

点击上面↑「爱开发」关注我们每晚10点，捕获技术思考和创业资源洞察什么是ThreadLocalThreadLocal是一个本地线程副本变量工具类，各个线程都拥有一份线程私有的数

Java学习的正确打开方式

在博主认为，对于入门级学习java的最佳学习方法莫过于视频+博客+书籍+总结，前三者博主将淋漓尽致地挥毫于这篇博客文章中，至于总结在于个人，实际上越到后面你会发现学习的最好方式就是阅读参考官方文档其次就是国内的书籍，博客次之，这又是一个层次了，这里暂时不提后面再谈。博主将为各位入门java保驾护航，各位只管冲鸭！！！上天是公平的，只要不辜负时间，时间自然不会辜负你。 何谓学习？博主所理解的学习，它是一个过程，是一个不断累积、不断沉淀、不断总结、善于传达自己的个人见解以及乐于分享的过程。

程序员必须掌握的核心算法有哪些？

由于我之前一直强调数据结构以及算法学习的重要性，所以就有一些读者经常问我，数据结构与算法应该要学习到哪个程度呢？，说实话，这个问题我不知道要怎么回答你，主要取决于你想学习到哪些程度，不过针对这个问题，我稍微总结一下我学过的算法知识点，以及我觉得值得学习的算法。这些算法与数据结构的学习大多数是零散的，并没有一本把他们全部覆盖的书籍。下面是我觉得值得学习的一些算法以及数据结构，当然，我也会整理一些看过

大学四年自学走来，这些私藏的实用工具/学习网站我贡献出来了

大学四年，看课本是不可能一直看课本的了，对于学习，特别是自学，善于搜索网上的一些资源来辅助，还是非常有必要的，下面我就把这几年私藏的各种资源，网站贡献出来给你们。主要有：电子书搜索、实用工具、在线视频学习网站、非视频学习网站、软件下载、面试/求职必备网站。 注意：文中提到的所有资源，文末我都给你整理好了，你们只管拿去，如果觉得不错，转发、分享就是最大的支持了。 一、电子书搜索 对于大部分程序员...

《奇巧淫技》系列-python！！每天早上八点自动发送天气预报邮件到QQ邮箱

此博客仅为我业余记录文章所用，发布到此，仅供网友阅读参考，如有侵权，请通知我，我会删掉。 补充 有不少读者留言说本文章没有用，因为天气预报直接打开手机就可以收到了，为何要多此一举发送到邮箱呢！！！那我在这里只能说：因为你没用，所以你没用！！！ 这里主要介绍的是思路，不是天气预报！不是天气预报！！不是天气预报！！！天气预报只是用于举例。请各位不要再刚了！！！ 下面是我会用到的两个场景： 每日下

Python 植物大战僵尸代码实现(2):植物卡片选择和种植

这篇文章要介绍的是： - 上方植物卡片栏的实现。 - 点击植物卡片，鼠标切换为植物图片。 - 鼠标移动时，判断当前在哪个方格中，并显示半透明的植物作为提示。

死磕YOLO系列，YOLOv1 的大脑、躯干和手脚

YOLO 是我非常喜欢的目标检测算法，堪称工业级的目标检测，能够达到实时的要求，它帮我解决了许多实际问题。 这就是 YOLO 的目标检测效果。它定位了图像中物体的位置，当然，也能预测物体的类别。 之前我有写博文介绍过它，但是每次重新读它的论文，我都有新的收获，为此我准备写一个系列的文章来详尽分析它。这是第一篇，从它的起始 YOLOv1 讲起。 YOLOv1 的论文地址：https://www.c

知乎高赞：中国有什么拿得出手的开源软件产品？(整理自本人原创回答)

知乎高赞：中国有什么拿得出手的开源软件产品？ 在知乎上，有个问题问“中国有什么拿得出手的开源软件产品（在 GitHub 等社区受欢迎度较好的）？” 事实上，还不少呢~ 本人于2019.7.6进行了较为全面的 回答 - Bravo Yeung，获得该问题下回答中得最高赞(236赞和1枚专业勋章)，对这些受欢迎的 Github 开源项目分类整理如下： 分布式计算、云平台相关工具类 1.SkyWalk

记一次腾讯面试：进程之间究竟有哪些通信方式？如何通信？ ---- 告别死记硬背

有一次面试的时候，被问到进程之间有哪些通信方式，不过由于之前没深入思考且整理过，说的并不好。想必大家也都知道进程有哪些通信方式，可是我猜很多人都是靠着”背“来记忆的，所以今天的这篇文章，讲给大家详细着讲解他们是如何通信的，让大家尽量能够理解他们之间的区别、优缺点等，这样的话，以后面试官让你举例子，你也能够顺手拈来。 1、管道 我们来看一条 Linux 的语句 netstat -tulnp | gr...

20行Python代码爬取王者荣耀全英雄皮肤

引言 王者荣耀大家都玩过吧，没玩过的也应该听说过，作为时下最火的手机MOBA游戏，咳咳，好像跑题了。我们今天的重点是爬取王者荣耀所有英雄的所有皮肤，而且仅仅使用20行Python代码即可完成。 准备工作 爬取皮肤本身并不难，难点在于分析，我们首先得得到皮肤图片的url地址，话不多说，我们马上来到王者荣耀的官网： 我们点击英雄资料，然后随意地选择一位英雄，接着F12打开调试台，找到英雄原皮肤的图片

网络（8）-HTTP、Socket、TCP、UDP的区别和联系

TCP/IP协议是传输层协议，主要解决数据如何在网络中传输，而HTTP是应用层协议，主要解决如何包装数据。 一、TCP与UDP的不同 1. 是否需要建立连接。 UDP在传送数据之前不需要先建立连接；TCP则提供面向连接的服务； 2. 是否需要给出确认 对方的传输层在收到UDP报文后，不需要给出任何确认，而 TCP需要给出确认报文，要提供可靠的、面向连接的传输服务。 3.虽然UDP不提供可靠交...

简明易理解的@SpringBootApplication注解源码解析（包含面试提问）

欢迎关注文章系列 ，关注我 《提升能力，涨薪可待》 《面试知识，工作可待》 《实战演练，拒绝996》 欢迎关注我博客，原创技术文章第一时间推出 也欢迎关注公 众 号【Ccww笔记】，同时推出 如果此文对你有帮助、喜欢的话，那就点个赞呗，点个关注呗！ 《提升能力，涨薪可待篇》- @SpringBootApplication注解源码解析 一、@SpringBootApplication 的作用是什

防劝退！数据结构和算法难理解？可视化动画带你轻松透彻理解！

大家好，我是 Rocky0429，一个连数据结构和算法都不会的蒟蒻… 学过数据结构和算法的都知道这玩意儿不好学，没学过的经常听到这样的说法还没学就觉得难，其实难吗？真难！ 难在哪呢？当年我还是个小蒟蒻，初学数据结构和算法的时候，在忍着枯燥看完定义原理，之后想实现的时候，觉得它们的过程真的是七拐八绕，及其难受。 在简单的链表、栈和队列这些我还能靠着在草稿上写写画画理解过程，但是到了数论、图...

西游记团队中如果需要裁掉一个人，会先裁掉谁？

2019年互联网寒冬，大批企业开始裁员，下图是网上流传的一张截图： 裁员不可避免，那如何才能做到不管大环境如何变化，自身不受影响呢？ 我们先来看一个有意思的故事，如果西游记取经团队需要裁员一名，会裁掉谁呢，为什么？ 西游记团队组成： 1.唐僧 作为团队teamleader，有很坚韧的品性和极高的原则性，不达目的不罢休，遇到任何问题，都没有退缩过，又很得上司支持和赏识(直接得到唐太宗的任命，既给

开挂的人生！那些当选院士，又是ACM/IEEE 双料Fellow的华人学者们

昨日，2019年两院院士正式官宣，一时间抢占了各大媒体头条。 朋友圈也是一片沸腾，奔走相告，赶脚比自己中了大奖还嗨皮！ 谁叫咱家导师就是这么厉害呢！！！ 而就在最近，新一年度的IEEE/ACM Fellow也将正式公布。 作为学术届的顶级荣誉，不自然地就会将院士与Fellow作比较，到底哪个含金量更高呢？ 学术君认为，同样是专业机构对学者的认可，考量标准不一，自然不能一概而论。 但...

聊聊C语言和指针的本质

坐着绿皮车上海到杭州，24块钱，很宽敞，在火车上非正式地聊几句。 很多编程语言都以 “没有指针” 作为自己的优势来宣传，然而，对于C语言，指针却是与生俱来的。 那么，什么是指针，为什么大家都想避开指针。 很简单， 指针就是地址，当一个地址作为一个变量存在时，它就被叫做指针，该变量的类型，自然就是指针类型。 指针的作用就是，给出一个指针，取出该指针指向地址处的值。为了理解本质，我们从计算机模型说起...

Python语言高频重点汇总

Python语言高频重点汇总 GitHub面试宝典仓库——点这里跳转 文章目录Python语言高频重点汇总**GitHub面试宝典仓库——点这里跳转**1. 函数-传参2. 元类3. @staticmethod和@classmethod两个装饰器4. 类属性和实例属性5. Python的自省6. 列表、集合、字典推导式7. Python中单下划线和双下划线8. 格式化字符串中的%和format9.

究竟你适不适合买Mac？

我清晰的记得，刚买的macbook pro回到家，开机后第一件事情，就是上了淘宝网，花了500元钱，找了一个上门维修电脑的师傅，上门给我装了一个windows系统。。。。。。 表砍我。。。 当时买mac的初衷，只是想要个固态硬盘的笔记本，用来运行一些复杂的扑克软件。而看了当时所有的SSD笔记本后，最终决定，还是买个好（xiong）看（da）的。 已经有好几个朋友问我mba怎么样了，所以今天尽量客观

代码详解：如何用Python快速制作美观、炫酷且有深度的图表

全文共12231字，预计学习时长35分钟生活阶梯（幸福指数）与人均GDP（金钱）正相关的正则图本文将探讨三种用Python可视化数据的不同方法。以可视化《2019年世界幸福报告》的数据为例，本文用Gapminder和Wikipedia的信息丰富了《世界幸福报告》数据，以探索新的数据关系和可视化方法。《世界幸福报告》试图回答世界范围内影响幸福的因素。报告根据对“坎特里尔阶梯问题”的回答来确定幸...

程序员一般通过什么途径接私活？

二哥，你好，我想知道一般程序猿都如何接私活，我也想接，能告诉我一些方法吗？ 上面是一个读者“烦不烦”问我的一个问题。其实不止是“烦不烦”，还有很多读者问过我类似这样的问题。 我接的私活不算多，挣到的钱也没有多少，加起来不到 20W。说实话，这个数目说出来我是有点心虚的，毕竟太少了，大家轻喷。但我想，恰好配得上“一般程序员”这个称号啊。毕竟苍蝇再小也是肉，我也算是有经验的人了。 唾弃接私活、做外

（经验分享）作为一名普通本科计算机专业学生，我大学四年到底走了多少弯路

今年正式步入了大四，离毕业也只剩半年多的时间，回想一下大学四年，感觉自己走了不少弯路，今天就来分享一下自己大学的学习经历，也希望其他人能不要走我走错的路。 （一）初进校园 刚进入大学的时候自己完全就相信了高中老师的话：“进入大学你们就轻松了”。因此在大一的时候自己学习的激情早就被抛地一干二净，每天不是在寝室里玩游戏就是出门游玩，不过好在自己大学时买的第一台笔记本性能并不是很好，也没让我彻底沉...

如何写一篇技术博客，谈谈我的看法

前言 只有光头才能变强。 文本已收录至我的GitHub精选文章，欢迎Star：https://github.com/ZhongFuCheng3y/3y 我一直推崇学技术可以写技术博客去沉淀自己的知识，因为知识点实在是太多太多了，通过自己的博客可以帮助自己快速回顾自己学过的东西。 我最开始的时候也是只记笔记，认为自己能看得懂就好。但如果想验证自己是不是懂了，可以写成技术博客。在写技术博客的...

字节跳动面试官这样问消息队列：分布式事务、重复消费、顺序消费，我整理了一下

你知道的越多，你不知道的越多 点赞再看，养成习惯 GitHub上已经开源 https://github.com/JavaFamily 有一线大厂面试点脑图、个人联系方式和人才交流群，欢迎Star和完善 前言 消息队列在互联网技术存储方面使用如此广泛，几乎所有的后端技术面试官都要在消息队列的使用和原理方面对小伙伴们进行360°的刁难。 作为一个在互联网公司面一次拿一次Offer的面霸...

面试还搞不懂redis，快看看这40道面试题（含答案和思维导图）

Redis 面试题 1、什么是 Redis?. 2、Redis 的数据类型？ 3、使用 Redis 有哪些好处？ 4、Redis 相比 Memcached 有哪些优势？ 5、Memcache 与 Redis 的区别都有哪些？ 6、Redis 是单进程单线程的？ 7、一个字符串类型的值能存储最大容量是多少？ 8、Redis 的持久化机制是什么？各自的优缺点？ 9、Redis 常见性...

大学四年自学走来，这些珍藏的「实用工具/学习网站」我全贡献出来了

知乎高赞：文中列举了互联网一线大厂程序员都在用的工具集合，涉及面非常广，小白和老手都可以进来看看，或许有新收获。

互联网公司的裁员，能玩出多少种花样？

裁员，也是一门学问，可谓博大精深！以下，是互联网公司的裁员的多种方法：-正文开始-135岁+不予续签的理由：千禧一代网感更强。95后不予通过试用期的理由：已婚已育员工更有责任心。2通知接下来要过苦日子，让一部分不肯同甘共苦的员工自己走人，以“兄弟”和“非兄弟”来区别员工。3强制996。员工如果平衡不了工作和家庭，可在离婚或离职里二选一。4不布置任何工作，但下班前必须提交千字工作日报。5不给活干+...

【设计模式】单例模式的八种写法分析

网上泛滥流传单例模式的写法种类，有说7种的，也有说6种的，当然也不排除说5种的，他们说的有错吗？其实没有对与错，刨根问底，写法终究是写法，其本质精髓大体一致！因此完全没必要去追究写法的多少，有这个时间还不如跟着宜春去网吧偷耳机、去田里抓青蛙得了，一天天的....

《面试宝典》：检验是否为合格的初中级程序员的面试知识点，你都知道了吗？查漏补缺

欢迎关注文章系列，一起学习 《提升能力，涨薪可待篇》 《面试知识，工作可待篇》 《实战演练，拒绝996篇》 也欢迎关注公 众 号【Ccww笔记】，原创技术文章第一时间推出 如果此文对你有帮助、喜欢的话，那就点个赞呗，点个关注呗！ 《面试知识，工作可待篇》-Java笔试面试基础知识大全 前言 是不是感觉找工作面试是那么难呢？ 在找工作面试应在学习的基础进行总结面试知识点，工作也指日可待，欢...

关于研发效能提升的思考

研发效能提升是最近比较热门的一个话题，本人根据这几年的工作心得，做了一些思考总结，由于个人深度有限，暂且抛转引入。 三要素 任何生产力的提升都离不开这三个因素：人、流程和工具，少了其中任何一个因素都无法实现。 人，即思想，也就是古人说的“道”，道不同不相为谋，是制高点，也是高层建筑的基石。 流程，即方法，也是古人说的“法”。研发效能的提升，也就是要提高投入产出比，既要增加产出，也要减...

微博推荐算法简述

在介绍微博推荐算法之前，我们先聊一聊推荐系统和推荐算法。有这样一些问题：推荐系统适用哪些场景？用来解决什么问题、具有怎样的价值？效果如何衡量？ 推荐系统诞生很早，但真正被大家所重视，缘起于以”facebook”为代表的社会化网络的兴起和以“淘宝“为代表的电商的繁荣，”选择“的时代已经来临，信息和物品的极大丰富，让用户如浩瀚宇宙中的小点，无所适从。推荐系统迎来爆发的机会，变得离用户更近： 快...

GitHub 标星 1.6w+，我发现了一个宝藏项目，作为编程新手有福了！

大家好，我是 Rocky0429，一个最近老在 GitHub 上闲逛的蒟蒻… 特别惭愧的是，虽然我很早就知道 GitHub，但是学会逛 GitHub 的时间特别晚。当时一方面是因为菜，看着这种全是英文的东西难受，不知道该怎么去玩，另一方面是一直在搞 ACM，没有做一些工程类的项目，所以想当然的以为和 GitHub 也没什么关系（当然这种想法是错误的）。 后来自己花了一个星期看完了 Pyt...

相关热词 c# 数组类型 泛型约束 c#的赛狗日程序 c# 传递数组 可变参数 c# 生成存储过程 c# list 补集 c#获得所有窗体 c# 当前秒数转成年月日 c#中的枚举 c# 计算校验和 连续随机数不重复c#