SCC即强连通分量，即一个图的子图，其中的点能相互到达，全称是strongly connected component。
Tarjan算法是用来找出图的SCC。
伪代码
int index = 0; //全局变量istack s; //全局堆栈svoid tarjan(vertex v){ LOW[v] = DFN[v] = ++index; //初始化LOW和DFN s.push(v); for(所有与v相连的节点w){ if(w没有被访问过){ //(v, w)是搜索树上的边 tarjan(w); LOW[v] = min(LOW[v], LOW[w]); } else if(DFN[w] < DFN[v]){ //(v, w)是交叉边或后向边，判断剔除了无用的前向边 if(w in s) LOW[v] = min(LOW[v], DFN[w]) } } if(DFN[v] == LOW[v]){ while(s.top() >= v){ //移除栈内元素直到v，构成一个强连通分量 // s.pop(); } }}
实际上LOW[v] = min(LOW[v], DFN[w])这句可以写成LOW[v] = min(LOW[v], LOW[w])，只要保证LOW[v]比DFN[v]小就可以。
题目
POJ 2186 Popular Cows
找出受所有人欢迎的奶牛，用tarjan缩点，缩点后的图里如果只有一个出度为0，那就把该缩点包含的点的个数输出，否则输出0。
#include#include #include #include using namespace std;const int N = 10010;const int M = 50005;struct data{ int to,next;} tu[M];int head[N],ip;int dfn[N],low[N];//dfn[]表示深搜的步数，low[u]表示u或u的子树能够追溯到的最早的栈中节点的次序号int sccno[N];//缩点数组，表示某个点对应的缩点值int cnt[N];//这个缩点有几个点组成int step;int scc_cnt;//强连通分量个数int o[N];int n,m,num,ans;void init(){ memset(head,-1,sizeof head); scanf("%d%d",&n,&m); for(int i=1; i<=m; i++) { int u,v; scanf("%d%d",&u,&v); tu[ip].to=v,tu[ip].next=head[u],head[u]=ip++; }}stack S;void dfs(int u){ dfn[u]=low[u]=++step; S.push(u); for(int i=head[u]; i!=-1; i=tu[i].next) { int v=tu[i].to; if(!dfn[v]) { dfs(v); low[u]=min(low[u],low[v]); } else if(!sccno[v]) low[u]=min(low[u],low[v]); } if(low[u]==dfn[u]) { scc_cnt++; while(1) { int x=S.top(); S.pop(); sccno[x]=scc_cnt; cnt[scc_cnt]++; if(x==u)break; } }}void solve(){ for(int u=1; u<=n; u++) for(int i=head[u]; i!=-1; i=tu[i].next) { int v=tu[i].to; if(sccno[u]!=sccno[v]){ o[sccno[u]]++; break; } } for(int i=1; i<=scc_cnt; i++) if(o[i]==0) { ans=i; num++; if(num>1)break; } if(num==1) ans= cnt[ans]; else ans=0;}int main(){ //freopen("in.txt","r",stdin); init(); for(int i=1; i<=n; i++) if(!dfn[i])dfs(i); solve(); printf("%d\n",ans); return 0;}