今天学了Kosaraju算法！曼波
模板：p2863
对于一个图怎么求它有多少个强连通分量呢？！
1，什么是强连通分量？
• 强连通：在一个有向图G中，如果两个顶点u、v间存在
一条u到v的路径且也存在一条v到u的路径，则称这两个
顶点u、v是强连通的
• 强连通图：有向图G的任意两个顶点都强连通，则称G是
一个强连通图
• 极大强连通子图：G是一个极大强连通子图，当且仅当G
是一个强连通子图且不存在另一个强连图子图G’ G
• 强连通分量：有向非强连通图的极大强连通子图，称为
强连通分量；
Kosaraju算法
一种使用两次dfs的求解方法！一次在原图上，一次在反图上；
然后我们在第一次dfs时记录所有结点的退出顺序，并且在第二次在反图上dfs时按照退出顺序的逆序遍历；
这样第二次就是拓扑序从小到大做，每次就能恰好得到一个强连通分量；
代码：
#include<bits/stdc++.h>
using namespace std;
int n,m,cnt;
int t=0,ans=0;
vector<int> g[100005];
vector<int> gp[100005];//存反图
int b[50005],s[50005];
void dfs1(int x){b[x]=1;for(int i=0;i<g[x].size();i++){if(!b[g[x][i]]) dfs1(g[x][i]); }s[++t]=x;//记录退出顺序return;
}
void dfs2(int x){b[x]=1;for(int i=0;i<gp[x].size();i++){if(!b[gp[x][i]]){cnt++;dfs2(gp[x][i]); }}return;
}
int main(){memset(g,0,sizeof(g));memset(gp,0,sizeof(gp));cin>>n>>m;int x,y;for(int i=1;i<=m;i++){cin>>x>>y;g[x].push_back(y);gp[y].push_back(x);}for(int i=1;i<=n;i++){//第一次dfsif(!b[i]) dfs1(i);}memset(b,0,sizeof(b));for(int i=t;i>=1;i--){//第二次dfscnt=0;if(!b[s[i]]){dfs2(s[i]);if(cnt>0) ans++;//题目要求判断点数大于一} }cout<<ans;return 0;
}
听说tarjan更好呢...题解也全是tarjan
下次再学吧~