https://www.cnblogs.com/1pha/articles/7818320.html
只适用于有向图
#include<stdio.h>//求一个图存在多少个强连通分量
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 1000000
vector<int>mp[maxn];
int ans[maxn];
int vis[maxn];
int dfn[maxn];
int low[maxn];
int n,m,cnt,sig,tt;void Tarjian(int u)
{vis[u] = 1;low[u] = dfn[u] = cnt++;for(int i = 0;i< mp[u].size();i++){int v = mp[u][i];if(vis[v] == 0) Tarjian(v);if(vis[v] == 1) low[u] = min(low[u],low[v]);}if(dfn[u] == low[u]){sig++;}
}
void init()
{memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));for(int i = 1;i<=n;i++) mp[i].clear();
}
void solve()
{sig = 0,cnt = 1,tt = -1;for(int i=1;i<=n;i++){if(vis[i] == 0){Tarjian(i);}}printf("%d\n",sig);
}int main()
{while(~scanf("%d",&n)){if(n==0)break;scanf("%d",&m);init();for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);mp[x].push_back(y);}solve();}
}
POJ2553
https://cn.vjudge.net/problem/POJ-2553
#include<stdio.h>//求一个图存在多少个强连通分量
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define maxn 1000000
vector<int>mp[maxn];
int ans[maxn];
int degree[maxn]; //记录度
int clocr[maxn];//染色 判断两点是否强连通
int Stack[maxn];
int vis[maxn];
int dfn[maxn];
int low[maxn];
int n,m,cnt,sig,tt;void init()
{memset(vis,0,sizeof(vis));memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));memset(degree,0,sizeof(degree));memset(clocr,0,sizeof(clocr));memset(Stack,0,sizeof(Stack));for(int i = 1;i<=n;i++) mp[i].clear();
}void Tarjian(int u)
{vis[u] = 1;low[u] = dfn[u] = cnt++;Stack[++tt] = u;for(int i = 0;i< mp[u].size();i++){int v = mp[u][i];if(vis[v] == 0) Tarjian(v);if(vis[v] == 1) low[u] = min(low[u],low[v]);}if(dfn[u] == low[u])//找到强连通图 {sig++;do{clocr[Stack[tt]] = sig;vis[Stack[tt]] = -1;}while(Stack[tt--] != u); //染色}
}void solve()
{sig = 0,cnt = 1,tt = -1;for(int i=1;i<=n;i++) {if(vis[i] == 0){Tarjian(i);}}for(int i = 1;i<=n;i++){for(int j = 0;j<mp[i].size();j++){int v = mp[i][j];if(clocr[i] != clocr[v]) //如果不是同一个强连通 算上边{degree[clocr[i]]++;}}}int tot = 0;for(int i = 1;i<=sig;i++){if(degree[i] > 0) continue; //出度大于0 for(int j = 1;j<=n;j++) //等于0 查找强连通里的点{if(clocr[j] == i){ans[tot++] = j;}}}sort(ans,ans+tot);for(int i = 0;i<tot;i++){if(i == 0) printf("%d",ans[i]);else printf(" %d",ans[i]);}printf("\n");
}int main()
{while(~scanf("%d",&n)){if(n==0)break;scanf("%d",&m);init();for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);mp[x].push_back(y);}solve();}
}