输入一个有向图,计算每个节点所在强连通分量的编号,输出强连通分量的个数
#include<iostream> #include<cstring> #include<vector> using namespace std; ; struct Edge{ int go,next; }; ,book[maxn]; vector<int> S; vector<int> G[maxn],G2[maxn]; void dfs(int u) { vis[u]=; ;i<G[u].size();i++){ int go=G[u][i]; if(!vis[go]) dfs(go); } S.push_back(u); } void dfs2(int u) { book[u]=count; ;i<G2[u].size();i++){ int go=G2[u][i]; if(!book[go]) dfs2(go); } } void init() { memset(vis,,sizeof(vis)); memset(book,,sizeof(book)); } int main() { int n,m,a,b; scanf("%d %d",&n,&m); init(); ;i<=m;i++) { scanf("%d %d",&a,&b); G[a].push_back(b); G2[b].push_back(a); } ;i<=n;i++) if(!vis[i]) dfs(i); ;i>=;i--) if(!book[S[i]]){ count++; dfs2(S[i]); } cout<<count; ; }