强连通分量（scc）
缩点
建新图
找入度为0的点
大功告成
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<vector> #include<stack> using namespace std; inline int read(){ int t=1,num=0;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();} return num*t; } const int N=100010; inline int min(int a,int b){return a<b?a:b;} vector<int> g[N];stack<int> s; int pre[N],low[N],biao[N],t=0,cnt=0,d[N]; void dfs(int x){ pre[x]=low[x]=++t;s.push(x); for(int i=0;i<g[x].size();i++){ int y=g[x][i]; if(!pre[y]){dfs(y);low[x]=min(low[x],low[y]);} else if(!biao[y])low[x]=min(low[x],pre[y]); } if(low[x]==pre[x]){ cnt++;int S=-1; while(S!=x){ S=s.top();s.pop(); biao[S]=cnt; } } } int main() { int n=read(),m=read(); for(int i=1;i<=m;i++){ int x=read(),y=read(); g[x].push_back(y); } for(int i=1;i<=n;i++) if(!pre[i])dfs(i); for(int i=1;i<=n;i++) for(int j=0;j<g[i].size();j++) if(biao[i]!=biao[g[i][j]]) d[biao[g[i][j]]]++; int ans=0; for(int i=1;i<=cnt;i++) if(!d[i])ans++; printf("%d\n",ans); return 0; }
本文由Yzyet编写，网址为www.cnblogs.com/Yzyet。非Yzyet同意，禁止转载，侵权者必究。
强连通分量——消息扩散(洛谷_2002)——tarjan求scc
原文：http://www.cnblogs.com/Yzyet/p/7413158.html