有向图——强连通分量
??? 有向图的强连通分量(strongly?connected components)
在有向图G中，如果两个顶点vi,vj间(vi!=vj)有一条从vi到vj的路径，同时还有一条从vj到vi的路径(顶点相互可达)，则称两个顶点强连通。如果有向图G的每对顶点都强连通，称G是个强连通图。非强连通图有向图的极大强连通子图，称为强连通分量。
??? 求解强连通分量的算法主要有三种：Kosaraju，Tarjan，Gabow。下面介绍Tarjan算法。
??? Tarjan算法基于图的深度遍历。定义dfn[u]是结点u的时间戳，low[u]为u和u的子树能够追溯到的最早的栈中结点的时间戳。
??? low[u] = min{dfn[u], low[v](u,v为树枝边，u为v的父节点), dfn[v](u,v为指向栈中结点的后向边)}；
??? 当dfn[u] == low[u]时，以u为根的搜索子树上所有结点是一个强连通分量。
?
关于Tarjan算法的详细介绍，参考:
http://hi.baidu.com/escorter2009/blog/item/f35951dc5bdb3de677c63826.html
?
POJ2186
题目大意：有n头牛，每头牛都希望自己受欢迎，输入a b表示a认为b受欢迎。要求出受其它所有牛欢迎的牛的个数。
解：首先求强连通分量，分量中每头牛都受分量中其它牛的欢迎。分量之间至多有一条有向边。那么显然需要找出出度为0的强连通分量，若有大于1的出度为0的强连通分量，这两个连通分量互相不认为对方受欢迎，显然个数为0；则有且仅有一个入读度为0的强连通分量时，该强连通分量的结点数即为解。
//出度为0的所有scc#include <iostream>const int MAX = 5005;int n,m;struct Edge{int to;int next;}e[MAX*MAX];int index[MAX],edgeNum;int low[MAX],dfn[MAX],seq;int stack[MAX],top;bool inStack[MAX];int belong[MAX],outdegree[MAX],cnt;int result[MAX],count;int min(int x, int y){return x < y ? x : y;}void addEdge(int from, int to){e[edgeNum].to = to;e[edgeNum].next = index[from];index[from] = edgeNum++;}void Tarjan(int u){low[u] = dfn[u] = seq++;stack[top++] = u;inStack[u] = true;for(int i = index[u]; i != -1; i = e[i].next){int w = e[i].to;if(dfn[w] < 0){Tarjan(w);low[u] = min(low[u],low[w]);}else if(inStack[w])//如果节点w还在栈内low[u] = min(low[u],dfn[w]);}if(low[u] == dfn[u]){int v;cnt++;do{top--;v = stack[top];inStack[v] = false;belong[v] = cnt;}while(u != v);}}void solve(){int i,j;for(i = 1; i <= n; i++)if(dfn[i] < 0)Tarjan(i);for(i = 1; i <= n; i++){for(j = index[i]; j != -1; j = e[j].next){if(belong[i] != belong[e[j].to])outdegree[belong[i]]++;}}for(i = 1; i <= n; i++){if(outdegree[belong[i]] == 0)result[count++] = i;}}int main(){int i,j;int from,to;while(true){scanf("%d",&n);if(n==0)break;edgeNum = top = seq = count = cnt =0;memset(dfn,-1,sizeof(dfn));memset(index,-1,sizeof(index));memset(inStack,0,sizeof(inStack));memset(belong,0,sizeof(belong));memset(outdegree,0,sizeof(outdegree));scanf("%d",&m);for(i = 0; i < m; i++){scanf("%d %d",&from,&to);addEdge(from,to);}solve();if(count == 0)printf("\n");else{for(i = 0; i < count-1; i++)printf("%d ",result[i]);printf("%d\n",result[i]);}}return 0;}?
?
?
?
?