数据结构课设有向图强连通分量求解

图连通性算法及应用图是计算机科学领域中常见的数据结构，用于表示对象之间的关系。

在图论中，图的连通性是一个重要的概念，指的是在图中任意两个顶点之间是否存在路径。

图连通性算法是为了判断图中的连通性而设计的算法，并且在实际应用中有着广泛的应用。

一、连通性的定义与分类在图论中，连通性有两种常见的定义方式：强连通性和弱连通性。

强连通性是指在有向图中，任意两个顶点之间存在互相可达的路径；弱连通性是指在有向图中，将其所有有向边的方向忽略后，剩下的无向图是连通的。

本文将重点介绍无向图的连通性算法及其应用。

二、连通性算法的原理1. 深度优先搜索（DFS）深度优先搜索是最常用的连通性算法之一。

它从图中的一个顶点开始，沿着一条未访问过的边深入图中的下一个顶点，直到无法深入为止，然后回溯至上一个顶点，继续深入其他未访问过的顶点。

通过深度优先搜索算法，我们可以得到一个图的连通分量，从而判断图是否连通。

2. 广度优先搜索（BFS）广度优先搜索同样是常用的连通性算法之一。

它从图中的一个顶点开始，沿着一条未访问过的边遍历与该顶点直接相邻的所有顶点，然后再以这些相邻顶点为起点，继续遍历它们的相邻顶点，直到遍历完所有连通的顶点。

通过广度优先搜索算法，我们可以得到一个图的层次遍历树，从而判断图是否连通。

三、连通性算法的应用1. 社交网络分析在社交网络分析中，连通性算法可以用来判断一个社交网络中是否存在分割成多个互不相连的社群。

通过判断社交网络的连通性，我们可以发现隐藏在社交网络背后的关系网络，从而更好地理解和分析社会关系。

2. 网络路由优化在计算机网络中，连通性算法可以用来判断网络节点之间的连通性。

通过分析网络的拓扑结构，我们可以选择合适的路由算法，从而实现快速且可靠的数据传输。

3. 图像分割在计算机视觉和图像处理中，连通性算法可以用来判断图像中的连通区域。

通过判断图像的连通性，我们可以对图像进行分割和提取，从而实现目标检测和图像识别等应用。

求强连通分量的几种算法的实现与分析作者：陈燕,江克勤来源：《电脑知识与技术》2011年第09期摘要：有向图的强连通性是图论中的经典问题，有着很多重要的应用。

该文给出了求强连通分量的Kosaraju、Tarjan和Gabow三个算法的具体实现，并对算法的效率进行了分析。

关键词：强连通分量；深度优先搜索；Kosaraju算法；Tarjan算法；Gabow算法中图分类号：TP312文献标识码：A文章编号：1009-3044(2011)09-2140-03The Implementation and Analysis of Several Algorithms About Strongly Connected Components CHEN Yan1, JIANG Ke-qin2(1.Nanjing Health Inspection Bureau, Nanjing 210003, China; 2.School of Computer and Information, Anqing Teachers College, Anqing 246011, China)Abstract: Digraph of strong connectivity is the classic problems in graph theory, which arises in many important applications. In this paper, the detailed implementation of Kosaraju, Tarjan and Gabow algorithms is discussed for solving strongly connected components, and the efficiency of three algorithms is analyzed.Key words: strongly connected components; depth first search; Kosaraju; Tarjan; Gabow图的连通性是图论中的经典问题，所谓连通性，直观地讲，就是“连成一片”。

求有向图的强连通分量的经典算法——Kosaraju算法一、Kosaraju算法步骤：Step1、对有向图G做dfs（深度优先遍历），记录每个结点结束访问的时间Step2、将图G逆置，即将G中所有弧反向。

Step3、按Step1中记录的结点结束访问时间从大到小对逆置后的图做dfs Step4、得到的遍历森林中每棵树对应一个强连通分量。

相关概念：在dfs(bfs)算法中，一个结点的开始访问时间指的是遍历时首次遇到该结点的时间，而该结点的结束访问时间则指的是将其所有邻接结点均访问完的时间。

二、Kosaraju算法求解过程实例下面结合实例说明Kosaraju算法的基本策略。

图1给出了一个有向图G。

图1 有向图GStep1：假设从DFS在遍历时按照字母顺序进行，根据Kosaraju算法，在步骤1中我们得到的遍历顺序可以表达为[A,[C,[B,[D,D],B],C],A][E,[F,[G,[H,H],G],F],E]在遍历序列中每一个结点出现了两次，其中第一次出现的时间为该结点的开始访问时间，第二次出现的时间为该结点的结束访问时间。

Step2：根据算法第2步，将图G逆置，得到对应的反向图G’如图2所示。

Step3：根据步骤1得到的遍历序列，按照结点结束访问时间递减排序后的结果为EFGHACBD下面，按照该结点序列顺序对逆置图G ’所深度优先遍历，得到的深度优先遍历森林如图3所示。

森林中共有4棵树，其中(a)和(d)只有一个结点，这里认为单结点也是一个强联通分量（在实际应用中可以根据实际需要将这种情况过滤掉）。

三、算法讨论问题1：以上图为例，第一遍搜索得到以A 为根的子序列（设为S1）和以E 为根的子树序列（设为S2），图反向后，再从E 开始搜索，能搜到的元素肯定不会包含S1的元素，为什么？答：因为S1中的点都不能到达E ，而第二遍搜索就是看哪些点能到达E ，所以搜不到S1中的点。

问题2：图反向后对A 进行深搜，尽管E 能到达A ，为什么搜不到E ？因为第一遍深搜时，A 不能达到E ，所以E 肯定位于A 的右边，而第二遍深搜是按照结束时间进行搜索的，在搜索A 之前，已经搜完E ，对E 设置了已经遍历标志，所以不会把E 并入A 的强联通分量。

实验报告课程名称数据结构实验项目名称有向图的强连通分量班级与班级代码14计算机实验班实验室名称（或课室）实验楼803 专业计算机科学与技术任课教师学号：姓名：实验日期：2015年12 月03 日广东财经大学教务处制姓名实验报告成绩评语：指导教师（签名）年月日说明：指导教师评分后，实验报告交院（系）办公室保存。

一、实验目的与要求采用邻接表存储的有向图。

二、实验内容（1）创建N个节点的空图DiGraph CreateGraph(int NumVertex)//创建一个N个节点的空图{DiGraph G;G = malloc( sizeof( struct Graph ) );if( G == NULL ) FatalError( "Out of space!!!" );G->Table = malloc( sizeof( struct TableEntry ) * NumVertex );if( G->Table == NULL )FatalError( "Out of space!!!" );G->NumVertex = NumVertex;G->NumEdge = 0;int i;for (i=0;i<NumVertex;i++){G->Table[i].Header=MakeEmpty(NULL);G->Table[i].V=i;}return G;}（2）在图G上执行DFS，通过对DFS生成森林的后序遍历对G的顶点编号。

//后序DFS遍历图G，并将节点按后序遍历的顺序编号int *PostDFS(DiGraph G){int NumVertex=G->NumVertex;int visited[NumVertex];int i;for (i=0;i<NumVertex;i++){visited[i]=0;//初始化，所有节点都未被访问过}int *post = malloc( sizeof( int ) * NumVertex );//用于存放后序DFS遍历时，节点的编号if( post == NULL ) FatalError( "Out of space!!!" );int postCounter=0;//定义一个内嵌的DFS函数void DFS (Vertex v)//从节点v出发执行DFS{visited[v]=1;//标记该节点被访问Position P = Header( G->Table[v].Header );if( !IsEmpty( G->Table[v].Header ) ){do//对节点v的所有邻接点递归调用DFS{P = Advance( P );Vertex w=Retrieve( P );if (visited[w]==0)//v的邻接点w未被访问过{DFS(w);}} while( !IsLast( P, G->Table[v].Header ) );}post[v]=postCounter;postCounter++;}Vertex j;for (j=0;j<NumVertex;j++)//从每个节点出发进行DFS，因为图G有可能不是连通的{if (visited[j]==0) DFS(j);}return post;}(3)求图G的强连通分量int *StrongConnectedComponent(DiGraph G)//求图G的强连通分量{//DFS后序遍历图G，并将节点按后序遍历的顺序编号存入post数组int *post=PostDFS(G);//求图G的逆置GRDiGraph GR=ReverseGraph(G);//按post编号从大到小顺序在GR上执行DFS，所得连通分量就是原图G的强连通分量int NumVertex=GR->NumVertex;int visited[NumVertex];int i;for (i=0;i<NumVertex;i++){visited[i]=0;//初始化，所有节点都未被访问过}int *sccID = malloc( sizeof( int ) * NumVertex );//用于标记强连通分量的数组if( sccID == NULL ) FatalError( "Out of space!!!" );int sccCounter=0;//定义一个内嵌的DFS函数void DFS (Vertex v)//从节点v出发执行DFS{visited[v]=1;//标记该节点被访问sccID[v]=sccCounter;Position P = Header( GR->Table[v].Header );if( !IsEmpty( GR->Table[v].Header ) ){do//对节点v的所有邻接点递归调用DFS{P = Advance( P );Vertex w=Retrieve( P );if (visited[w]==0)//v的邻接点w未被访问过{DFS(w);}} while( !IsLast( P, GR->Table[v].Header ) );}}int m;for (m=NumVertex-1;m>=0;m--)//按post编号从大到小顺序在GR上执行DFS，因为图G有可能不是连通的{Vertex n;for (n=0;n<NumVertex;n++){if (post[n]==m)//节点n的编号为当前最大值{if (visited[n]==0){DFS(n);sccCounter++;}}}}return sccID;}(4)测试函数main(){DiGraph G=CreateGraph(10);//插入15条边，参见教科书P248，图9-74InsertEdge(G,0,1);InsertEdge(G,0,3);InsertEdge(G,1,2);InsertEdge(G,1,5);InsertEdge(G,2,0);InsertEdge(G,2,3);InsertEdge(G,2,4);InsertEdge(G,3,4);InsertEdge(G,5,2);InsertEdge(G,6,5);InsertEdge(G,6,7);InsertEdge(G,7,5);InsertEdge(G,7,9);InsertEdge(G,8,7);InsertEdge(G,9,8);//插入15条边结束printf("输出图...\n");OutputGraph(G);printf("\n输出图的逆置...\n");DiGraph GR=ReverseGraph(G);OutputGraph(GR);printf("\n输出后序DFS编号...\n");int *pp=PostDFS(G);int i;for (i=0;i<G->NumVertex;i++)printf("%d---",pp[i]);printf("\n\n输出强连通分量编号...\n");int *scc=StrongConnectedComponent(G);for (i=0;i<G->NumVertex;i++)printf("%d~~~",scc[i]);printf("\n\n");}(5)测试截图四、实验中的问题及解决办法，疑问和猜想。

强连通算法--Tarjan个⼈理解+详解⾸先我们引⼊定义：1、有向图G中，以顶点v为起点的弧的数⽬称为v的出度，记做deg+（v）；以顶点v为终点的弧的数⽬称为v的⼊度，记做deg-（v）。

2、如果在有向图G中，有⼀条<u，v>有向道路，则v称为u可达的，或者说，从u可达v。

3、如果有向图G的任意两个顶点都互相可达，则称图 G是强连通图，如果有向图G存在两顶点u和v使得u不能到v，或者v不能到u，则称图G 是强⾮连通图。

4、如果有向图G不是强连通图，他的⼦图G2是强连通图，点v属于G2，任意包含v的强连通⼦图也是G2的⼦图，则乘G2是有向图G的极⼤强连通⼦图，也称强连通分量。

5、什么是强连通？强连通其实就是指图中有两点u，v。

使得能够找到有向路径从u到v并且也能够找到有向路径从v到u，则称u，v是强连通的。

然后我们理解定义：既然我们现在已经了解了什么是强连通，和什么是强连通分量，可能⼤家对于定义还是理解的不透彻，我们不妨引⼊⼀个图加强⼤家对强连通分量和强连通的理解：标注棕⾊线条框框的三个部分就分别是⼀个强连通分量，也就是说，这个图中的强连通分量有3个。

其中我们分析最左边三个点的这部分：其中1能够到达0,0也能够通过经过2的路径到达1.1和0就是强连通的。

其中1能够通过0到达2,2也能够到达1，那么1和2就是强连通的。

.........同理，我们能够看得出来这⼀部分确实是强连通分量，也就是说，强连通分量⾥边的任意两个点，都是互相可达的。

那么如何求强连通分量的个数呢？另外强连通算法能够实现什么⼀些基本操作呢？我们继续详解、接着我们开始接触算法，讨论如何⽤Tarjan算法求强连通分量个数：Tarjan算法，是⼀个基于Dfs的算法（如果⼤家还不知道什么是Dfs，⾃⾏百度学习），假设我们要先从0号节点开始Dfs，我们发现⼀次Dfs 我萌就能遍历整个图（树），⽽且我们发现，在Dfs的过程中，我们深搜到了其他强连通分量中，那么俺们Dfs之后如何判断他喵的哪个和那些节点属于⼀个强连通分量呢？我们⾸先引⼊两个数组：①dfn【】②low【】第⼀个数组dfn我们⽤来标记当前节点在深搜过程中是第⼏个遍历到的点。

求有向图的强连通分量个数（kosaraju算法）求有向图的强连通分量个数（kosaraju算法）1. 定义连通分量：在⽆向图中，即为连通⼦图。

上图中，总共有四个连通分量。

顶点A、B、C、D构成了⼀个连通分量，顶点E构成了⼀个连通分量，顶点F，G和H，I分别构成了两个连通分量。

强连通分量：有向图中，尽可能多的若⼲顶点组成的⼦图中，这些顶点都是相互可到达的，则这些顶点成为⼀个强连通分量。

上图中有三个强连通分量，分别是a、b、e以及f、g和c、d、h。

2. 连通分量的求解⽅法对于⼀个⽆向图的连通分量，从连通分量的任意⼀个顶点开始，进⾏⼀次DFS，⼀定能遍历这个连通分量的所有顶点。

所以，整个图的连通分量数应该等价于遍历整个图进⾏了⼏次（最外层的）DFS。

⼀次DFS中遍历的所有顶点属于同⼀个连通分量。

下⾯我们将介绍有向图的强连通分量的求解⽅法。

3. Kosaraju算法的基本原理我们⽤⼀个最简单的例⼦讲解Kosaraju算法显然上图中有两个强连通分量，即强连通分量A和强连通分量B，分别由顶点A0-A1-A2和顶点B3-B4-B5构成。

每个连通分量中有若⼲个可以相互访问的顶点（这⾥都是3个），强连通分量与强连通分量之间不会形成环，否则应该将这些连通分量看成⼀个整体，即看成同⼀个强连通分量。

我们现在试想能否按照⽆向图中求连通分量的思路求解有向图的强连通分量。

我们假设，DFS从强连通分量B的任意⼀个顶点开始，那么恰好遍历整个图需要2次DFS，和连通分量的数量相等，⽽且每次DFS遍历的顶点恰好属于同⼀个连通分量。

但是，我们若从连通分量A中任意⼀个顶点开始DFS，就不能得到正确的结果，因为此时我们只需要⼀次DFS就访问了所有的顶点。

所以，我们不应该按照顶点编号的⾃然顺序（0,1,2，……）或者任意其它顺序进⾏DFS，⽽是应该按照被指向的强连通分量的顶点排在前⾯的顺序进⾏DFS。

上图中由强连通分量A指向了强连通分量B。

数据结构课设有向图强连通分量求解数据结构课设：有向图强连通分量求解一、引言有向图是图论中的一种重要概念，强连通分量是有向图中的一个子图，其中任意两个顶点之间都存在一条有向路径。

在数据结构课设中，我们需要实现一个算法，能够求解给定有向图的强连通分量。

二、问题描述给定一个有向图G=(V,E)，其中V表示顶点的集合，E表示边的集合。

我们需要设计一个算法，能够找出图G中的所有强连通分量，并将其输出。

三、算法设计为了解决这个问题，我们可以使用Tarjan算法，该算法是一种经典的强连通分量求解算法。

下面是Tarjan算法的详细步骤：1. 初始化步骤：- 创建一个空栈S，用于存储访问过的顶点。

- 创建一个整数数组dfn和low，用于记录每个顶点的访问次序和最早访问到的祖先顶点的次序。

- 创建一个布尔数组inStack，用于标记顶点是否在栈中。

- 创建一个整数变量index，用于记录当前访问的次序。

2. 递归搜索步骤：- 遍历图中的每个顶点v，若v未被访问，则执行递归搜索函数Tarjan(v)。

- 在Tarjan(v)函数中，首先将v入栈，并标记v在栈中。

- 然后将dfn[v]和low[v]均设为index的值，并将index加1。

- 对于v的每个邻接顶点u，若u未被访问，则执行递归搜索函数Tarjan(u)。

- 在递归返回后，更新low[v]的值为v的所有邻接顶点u的low值的最小值。

- 若dfn[v]等于low[v]，则说明v是一个强连通分量的根节点，将栈中的顶点依次出栈，直到v为止，并将这些顶点构成一个强连通分量。

3. 输出结果：- 将找到的所有强连通分量输出。

四、算法分析Tarjan算法的时间复杂度为O(V+E)，其中V为顶点的数量，E为边的数量。

该算法通过深度优先搜索的方式遍历图中的每个顶点，同时使用dfn和low数组记录顶点的访问次序和最早访问到的祖先顶点的次序。

通过比较dfn和low数组的值，可以确定强连通分量的根节点，并将其输出。

求强连通分量1、Kosaraju算法对每个不在树中的点开始DFS一次，并记录离开各点的时间，这里是离开的时间，而不是到达时的，比如有图1->2 2->3 则1,2,3分别对应的时间是3 2 1,因为3没有出边，所以最先离开，其次是2,最后是1,DFS后，在同一棵树中的点，如果dfn[v]>dfn[u]则说明点从v有可能到达u,而这棵树中的dfn[]最大的点，肯定可以到达每个点，从而在原图的逆图中，每次都选没有访问过的最大的dfn值开始DFS,如果可达点x 则说明它们是强连通的void DFS_T(int u){int i,v;if(used[u])return ;used[u]=1;id[u]=scc;for(i=q[u];i!=-1;i=Tedge[i].pre){v=Tedge[i].d;if(!used[v])DFS_T(v);}}void DFS(int v){int i,u;if(used[v])return ;used[v]=1;for(i=p[v];i!=-1;i=edge[i].pre){u=edge[i].d;if(!used[u])DFS(u);}order[++num]=v;}int Kosaraju(){int i,j,k,v,u;memset(used,0,sizeof(used));num=0;for(i=1;i<=n;++i)if(!used[i])DFS(i);memset(used,0,sizeof(used));memset(id,0,sizeof(id));scc=0;for(i=num;i>=1;--i)if(!used[order[i]])scc++,DFS_T(order[i]);}2、Tarjan算法dfn[v]记录到达点v的时间，跟上面的离开不同，low[v]表示通过它的子结点可以到达的所有点中时间最小值，即low[i]=min(low[i],low[u]),u为v的了孙，初始化时low[v]=dfn[u]。

典型算法与ACM题目解析(02)—有向图的强连通分量上一篇:典型算法与ACM题目解析(01)—寻找最大流的标号法下一篇:关于STL中优先队列的用法作者:dzf 阅读次数:87 时间:2006-11-27 21:23:49 算法园地这道题是POJ的2186题，题意是说，有一群牛，总数为N(N<=10000),题目数据给出牛之间的关系，比如说1仰慕2，2仰慕3等等，设这种仰慕是可以传递的，如果1仰慕2，那么1也会同时仰慕2仰慕的那些牛，如果一头牛被所有的牛都仰慕，那么它将是最受欢迎的牛，题目要求的是有多少牛是"最受欢迎的"。

这道题目大家第一眼看到可能感觉直接模拟，但是由于数据量巨大，模拟的话肯定是过不了的，而且题目中还会出现环路的情况，比如1=>2,2=>3,3=>1，所以这解这道题最好的方法是使用有向图的强连通分量。

在同一个强连通分量里的所有的牛之间是互相仰慕的，我们将其缩为一点，并且只记录这一点的牛的数量，如果有最受欢迎的牛存在，那么这个图将是连通图，并且出度为零的点只有一个，我们可以用并查集来判是否连通，然后计算每个节点的出度，即可求出最受欢迎的牛的数量。

求强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法，其中Kosaraju算法要对原图和逆图都进行一次DFS，而另外两种算法只要DFS一次就可以了用了Gabow算法和Kosaraju算法各写了一遍在时间上Gabow算法是122ms,Kosaraju算法是61ms理论上Gabow算法要比Kosaraju快些的，因为Gabow算法只对原图进行一次DFS而Kosaraju要进行两次Gabow反而慢的原因可能是我用了STL里的stackPS:我没看懂Gabow算法，完全是对着书上写的代码如下:Kosaraju算法/*求有向图的强连通分量的Kosaraju‘s algorit hmBy Sempr ---- 2006.06.16*/#include <stdio.h>#include <string.h>#define G_size 100000#define V_size 11000typedef struct Graph{int id;int next;} Graph;typedef struct Edge{int s, e;} Edge;Edge E[G_size];Graph GA[G_size], GT[G_size];int N, M;int G_end;int order[V_size], id[V_size], vis[V_size], in[V_size]; int cnt, scnt, pos;void Insert(int s, int e) //建立原图和逆图{int p;p = s;while (GA[p].next)p = GA[p].next;GA[G_end].id = e;GA[p].next = G_end;p = e;while (GT[p].next)p = GT[p].next;GT[G_end].id = s;GT[p].next = G_end;G_end++;}void DFST(int x) //对逆图进行搜索{int p, q;vis[x] = 1;p = GT[x].next;while (p){q = GT[p].id;if (!vis[q])DFST(q);p = GT[p].next;}order[cnt++] = x;}void DFSA(int x) //对原图进行搜索{int p, q;vis[x] = 1;id[x] = cnt;p = GA[x].next;while (p){q = GA[p].id;if (!vis[q])DFSA(q);p = GA[p].next;}}void Solve() //主要过程{int s, e;int i;memset(GA, 0, sizeof(GA));memset(GT, 0, sizeof(GT));memset(E, 0, sizeof(E));G_end = N + 1;for (i = 0; i < M; i++){scanf("%d %d", &s, &e);E[i].s = s - 1;E[i].e = e - 1;Insert(s - 1, e - 1); }memset(vis, 0, sizeof(vis));cnt = 0;for (i = 0; i < N; i++){if (!vis[i]){DFST(i);}}memset(vis, 0, sizeof(vis));cnt = 0;for (i = N - 1; i >= 0; i--){if (!vis[order[i]]){DFSA(order[i]);cnt++;}}for (i = 0; i < M; i++){s = id[E[i].s];e = id[E[i].e];if (s != e){in[s]++;}}scnt = cnt;cnt = 0;for (i = 0; i < scnt; i++){if (in[i] == 0)pos = i;cnt++;}}if (cnt != 1){printf("0\n");}else{cnt = 0;for (i = 0; i < N; i++){if (in[id[i]] == pos){cnt++;}}printf("%d\n", cnt);}}int main(){while (EOF != scanf("%d %d", &N, &M))Solve();return 0;}Gabow算法/*求有向图的强连通分量的Gabow‘s algorithmBy Sempr ---- 2006.06.14*/#include <stdio.h>#include <algorithm>#include <stack>#define size 11000using namespace std;int N, M;typedef struct Node{int next;} Node;typedef struct Edge{int s, e;}Edge;Edge E[size * 6];Node G[size * 7];int pre[size], id[size];typedef stack<int> Stack;Stack S, path;int end;int cnt, scnt;int vis[size];int in[size];void Insert(int s, int e){int p = s;while (G[p].next){p = G[p].next;if (G[p].id == e){return;}}G[p].next = end;G[end].id = e;end++;}void scR(int w){int v;int p, t;pre[w] = cnt++;S.push(w);path.push(w);p = G[w].next;while (p){t = G[p].id;p = G[p].next;if (pre[t] == -1)scR(t);else if (id[t] == -1)while (pre[path.top()] > pre[t])path.pop();}if (path.top() == w)path.pop();elsereturn;do{id[v = S.top()] = scnt;S.pop();}while (v != w);scnt++;}void Gabow(){int i;memset(pre, -1, sizeof(pre));memset(id, -1, sizeof(id));cnt = 0;scnt = 0;while (!S.empty())S.pop();while (!path.empty())path.pop();for (i = 1; i <= N; i++){if (pre[i] == -1){scR(i);}}}void DFS(int w, int d){int p = G[w].next;d++;pre[w] = 1;if (d > cnt){cnt = d;}while (p){if (pre[G[p].id] != 1){DFS(G[p].id, d);}p = G[p].next;}}void Solve(){int i, s, e;int pos;memset(G, 0, sizeof(G));end = N + 10;memset(in, 0, sizeof(in));for (i = 0; i < M; i++){scanf("%d %d", &s, &e);E[i].s = s;E[i].e = e;Insert(s, e);}Gabow();memset(G, 0, sizeof(G));memset(pre, 0, sizeof(pre));end = scnt + 10;for (i = 0; i < M; i++){s = id[E[i].s];e = id[E[i].e];if (s != e){in[s]++;}}cnt = 0;for (i = 0; i < scnt; i++){if (in[i] == 0){pos = i;cnt++;}}if (cnt != 1){printf("0\n");}else{cnt = 0;for (i = 1; i <= N; i++){if (in[id[i]] == pos){cnt++;}}printf("%d\n", cnt);}}int main(){while (scanf("%d %d", &N, &M) != EOF)Solve();}return 0;}。

强连通分量【引言】本文讲述了求强连通分量的T arjan算法的思想以及一般过程，鉴于T arjan算法比较抽象，很多人明白怎么做但不理解为什么，所以本文以作者对T arjan算法的理解为主，供读者参考。

【正文】一、强连通分量的概念及性质。

概念：对于一个有向图G，存在点集P使得P中任意两点可以互相到达，则称P为一个强连通分量。

性质：如果对于一个点v，在v可以到达的点中，可以回到v的点和v一定属于同一个强连通分量；不可以回到v的点和v一定不属于一个强连通分量。

二、T arjan思想1.初步思想：利用搜索算法找到点v可以到达的所有点，再判断这些点中哪些可以回到v，并对符合条件的点进行染色，染成同色的点组成一个强连通分量。

2.深搜性质的利用：首先对点来做一些定义：白色点：表示该点还没有被访问过。

灰色点：表示正在处理该点发出的边，还没处理完。

黑色点：表示该点发出的所有边都处理完了。

深搜序：表示所有点由白变灰的顺序。

附属点：某点v从刚刚变成灰色到刚刚变成黑色这段时间内访问并处理过的所有点（不包括那些在v之前变灰或变黑的点，那些点在这段时间内只访问但没处理）性质1：从开始处理点v到处理完点v，所有的附属点都从白变黑。

性质2：在开始处理点v之前的那个时刻，所有的灰色点都可以到达点v，称这些灰色点为祖先点，并且这些祖先点构成一条链。

性质3：对于性质2所述的那些灰色点，在深搜序中靠前的点一定可以到达靠后的点。

这些性质有助于理解后面的思想。

3.引入进一步思想：首先是想法：对于当前点v，和它在同一个强连通分量里的点一定可以到达它。

这些点可以分为两部分：(1)性质2中那些灰色的点（祖先点） (2)其他可以到达v的点对于(2)那部分点，又可以分为两部分：和v在同一个强连通分量里的：这部分点将会变成v的附属点，所以不必考虑。

不和v在同一个强连通分量里的：这部分点显然不在考虑范畴内，但一会儿要用到。

所以，我们只需要考虑性质2中的祖先点！！！也就是说，v的附属点中，可以直接或间接到达那些祖先点的点，和v一定属于同一个强连通分量（通俗点说，就是v可以到它，它可以到 v的祖先，v的祖先又可以到v）。

7.4.2有向图的强连通分量。

//---------对图G做深度优先遍历,求有向图的强连通分量-------------- Boolean visited[MAX]; //访问标志数组。

Status (*VisitFunc)(int v); //函数变量。

int count;int finished[G.vexnum];//对图G做深度优先遍历。

Void DFSTraverse1(Graph G,Status(*Visit)(int v)){Count=0; //新加的。

VisitFunc=Visit; //使用全局变量VisitFunc,使DFS不必设函数指针参数。

for(v=0;v<G.vexnum;++v) visited[v]=FALSE; //访问标志数组初始化。

for(v=0;v<G.vexnum;++v)if(!visited[v]) DFS1(G,v); //对尚未访问的顶点调用DFS。

}//从第v个顶点出发递归地深度优先遍历图G..void DFS1(Graph G,int v){visited[v]=TRUE;VisitFunc(v); //访问第v个顶点。

for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w]) DFS1(G,w); //对v的尚未访问的邻接顶点w递归调用DFS. Finished[++count]=v; //新加的。

}// DFS1//------------------------------------反向搜索G--------Void DFSTraverse2(Graph G,Status(*Visit)(int v)){VisitFunc=Visit; //使用全局变量VisitFunc,使DFS不必设函数指针参数。

for(v=0;v<G.vexnum;++v) visited[v]=FALSE; //访问标志数组初始化。

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：有向图强连通分量求解院（系）：计算机学院专业：网络工程班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告目录1 算法分析 (2)1.1假设条件 (2)1.2算法描述 (2)1.2.1 有向图的存储结构 (2)1.2.2 深度优先遍历 (3)1.2.3 求解强连通分量 (3)2 系统设计 (4)2.1设计说明 (4)2.2数据结构描述 (4)2.3 MAIN()函数 (5)2.4邻接表和逆邻接表的建立 (7)2.5邻接表的遍历 (8)2.6逆邻接表的遍历 (9)3 系统实现 (12)3.1错误分析 (12)3.2实现结论 (12)参考文献 (13)附录（关键部分程序清单） (14)1 算法分析1.1假设条件有向图的强连通分量是有向图中的最大强连通子图。

而对于一个有向图G，如果对于每一对的Vi和V j∈V，Vi≠V j，从Vi到V j和V j到Vi都存在路径，则称G是强连通图。

有向图强连通分量求解的设置分为存储、输入以及输出三大部分。

（1）算法的存储分为对有向图的顶点的存储，对有向图的弧的存储和对整个有向图的链式存储。

（2）输入分为三大部分：第一，输入有向图的顶点数以及弧条数（均为整数）；第二，输入各个顶点的信息（均为字符型）；第三，输入每一条弧的弧尾与弧头所对应的顶点信息，即对各顶点进行链式存储时的顶点信息，并以输出0 0 为结束标志。

（3）算法的输出为该有向图的所有强连通分量（以集合的形式表示）以及该有向图是否是强连通图。

1.2算法描述该算法是为了实现输入一有向图到适当的存储结构中，判断该有向图是否强连通，若不是强连通图则求出该图的所有强连通分量并输出。

1.2.1 有向图的存储结构对于输入的有向图，利用链式的存储结构进行存储即对有向图的顶点、弧以及有向图进行链式的存储。

有向图顶点的存储中包含邻接点域(adjvex)指示与顶点Vi邻接的点在图中的位置和链域(next)指示下一条弧的结点。

For personal use only in study and research; not for commercial use算法学习：有向图的强连通分量DFSDFS就是深度优先搜索，裸的DFS是很启蒙的一个东西，所以就不废话了，直接给出它的程序：procedure dfs(x:longint);var j:longint;beginflag[x]:=1;for j:=1 to n doif (a[x,j]=1)and(flag[j]=0) thendfs(j);end;其中flag是是否遍历过的标记，a是邻接矩阵。

当然，在主程序中需要有这一句：for i:=1 to n doif flag[i]=0 then dfs(i);而不是直接的dfs(1)，因为节点1并不一定能到达所有节点。

这是初学者（我？）常犯的一个错误。

当然，DFS进行的顺序并不一定是按节点编号顺序。

一般按节点编号顺序DFS 只是为了方便，有时我们必须以不同的顺序进行DFS（比如下面将要谈到的Kosaraju算法）。

时间戳与点的分类设置全局变量time，初始值为0，当遇到一个事件点的时候就++1。

时间点分为两种：发现某一节点和结束某一节点（即在DFS过程的开头和结尾）。

发现节点x时，发现时间戳d[x]=time；结束节点x时，结束时间戳f[x]=time。

根据时间戳状态的不同可以将节点进行分类：白点==没有时间戳的节点==未遍历的节点灰点==仅有发现时间戳的节点==正在遍历以此节点为根的子树的节点黑点==有发现时间戳和结束时间戳的节点==完成的节点注意：点的分类随time增长而变化，且DFS结束后所有点都是黑点，所以用一个全局变量保存点的分类没有意义。

DFS过程中可以直接通过时间戳得知点的分类。

边的分类在 DFS过程中所有顶点和经过的边形成了一棵DFS树。

根据图中的边在DFS树中的位置和发现此边时入节点的分类（这里说的是有向图，每条边有出节点和入节点）将边分为四类：树枝==DFS树中的边==入节点为白点反向边==某一节点x到其DFS树中祖先y的边==入节点为灰点正向边==某一节点x到其DFS树中后代y的边==入节点为黑点==d[x]>d[y] 横叉边==某一节点x到DFS树中另一子树上节点y的边==入节点为黑点==d[x]<d[y]如下图：若以节点序号顺序进行DFS，则形成下面一棵DFS树（粗边是树枝，其他类型的边在旁边有说明）横叉边在图中是只能向左的，通过DFS的过程可以知道这一点。