简单易懂，良心题解

## [蕉个朋♂友](https://www.luogu.com.cn/blog/0lxy7/) ~~看见没有Kosaraju算法，赶紧来水一波；~~ ### 注：本题解只适用于像我一样刚入图论的萌新， ### 大佬请轻喷（Thanks♪(･ω･)ﾉ） ------------ ### 1. 什么是强连通分量 在有向图G中，如果两个顶点u，ｖ间有一条从ｕ到ｖ的有向路径，同时还有一条从ｖ到ｕ的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向非强连通图的极大强连通子图，称为强连通分量。（by-百度百科 ） #### 也可以这么说： 有向图中任意两点都连通的最大子图。特殊地，单个点也算一个强连通分量。（by-沃•资基硕得） 相信你一定知道了它的概念，想要更好了解，我们借助下图来康一康 “下图”：  #### 很明显：这里{1,2,3,4}是一个强连通分量，{5}，{6}也是； 因为：{1,2,3,4}中每一个元素都可以到达在此集合中所有的元素； {5}，{6}同理； 终于理解了概念，我们来康一康题目； [传送门](https://www.luogu.com.cn/problem/P2863) 显然：本题算一道模板题，只用求奶牛的强连通分量是就行了， # 但是 当我信心满满的测样例时，答案却是3； ## 为什么？ ### 看完了题目才发现：只有一头奶牛的集合不用算；~~可是只有我一个人掉这个坑~~； 好了，讲完了前面的概念和坑，我们来看看算法： 求强连通分量主要有两种算法 ## Kosaraju算法和Tarjan算法 ### 一.Kosaraju - 思想： 1.第一次对图G进行DFS遍历，并在遍历过程中，记录每一个点的退出顺序。 2.倒转每一条边的方向，构造出一个**反图**。然后按照**退出顺序的逆序**对反图进行第二次DFS遍历。每次遍历得到的那些点即属于**同一个**强连通分量。 ## code： 变量名起的不好，见谅^_^ ```c #include <iostream> #include <cstdio> #include <vector>//vector动态数组，不用关心大小; using namespace std; vector <int> s;//s 表示图遍历的退出顺序 int head[10005],tot,rtot,rhead[10005],fen[10005]; int cnt,ans,sum; /*tot,head,edge是原图链式前向星标准数组， rtot,rhead,redge是反图的链式前向星； fen[i]记录的是第i个元素属于第几个强连通分量； ans答案,sum用来记录，后面说;*/ bool vis[10005];//标志数组，vis[i]为第i个元素是否搜索到 struct Edge { int to,next; }edge[50005],redge[50005];//链式前向星 void add_edge(int x,int y)//建边 { edge[++tot].next=head[x]; edge[tot].to=y; head[x]=tot; } void radd_edge(int x,int y)//反图建边 { redge[++rtot].next=rhead[x]; redge[rtot].to=y; rhead[x]=rtot; } void dfs1(int x)//遍历并记录每个点的退出顺序 { if(vis[x])return ;//搜过了 vis[x]=true;//标记 for(int i=head[x];i;i=edge[i].next) dfs1(edge[i].to);//遍历 s.push_back(x);//记录退出顺序 } void dfs2(int x) { if(fen[x])return ;//这个点属于别的强连通分量，返回 fen[x]=cnt;//标记 sum+=1;//强连通分量值+1 for(int i=rhead[x];i;i=redge[i].next) { dfs2(redge[i].to);//遍历 } } int main() { cnt=0,tot=rtot=0; int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add_edge(x,y);//建边与反向建边 radd_edge(y,x); } for(int i=1;i<=n;i++)dfs1(i);//求退出顺序 for(int i=n;i>=1;i--) { if(!fen[s[i-1]])//这个点没搜过，开始遍历 {//注：vector是0下标开始，我喜欢1下标开始 cnt++;//多一个强连通分量； dfs2(s[i-1]);//遍历 if(sum>1)ans++;//如果不止一头奶牛在跳舞，答案+1 sum=0;//清零，为下一次做准备； } } printf("%d\n",ans);//输出 return 0; } ``` 本题使用了一种存储方式，称为：[链式前向星](https://blog.csdn.net/lookqaq/article/details/81304637) 最后： ~~厚脸皮~~ # 点赞，点赞，点赞！