poj2186：题目链接
题目大意：有n头奶牛，m个关系，A B表示A奶牛认为B是备受关注的，这个关系具有继承性，比如：A B 和 B C那么A奶牛也会认为C是备受关注的，问有多少头奶牛是受到除自己以外所以人关注的
首先进行强连通，那么每个连通块中的点都是受到该连通块中其它点的关注的，进行缩点，，原图变成一颗树，如果有且只有一个缩点以后的点的出度为0，那么这个点就是受到所有人关注的。记录下该点代表原图中的几个点，输出
不用考虑是否所有点在一个图中，因为如果不在一个图中，不会满足“有且只有一个缩点以后的点的出度为0”
#include <cstdio>#include <cstring>#include <algorithm>#include <stack>using namespace std ;struct node{int u , v ;int next ;} edge[51000] , tree[51000] ;int head[11000] , h_tree[11000] , cnt ;int dnf[11000] , low[11000] , time ;int vis[11000] , in[11000] , belong[11000] , num ;int sum[11000] ;stack <int> sta ;void init(){memset(head,-1,sizeof(head)) ;cnt = time = num = 0 ;memset(dnf,0,sizeof(dnf)) ;memset(low,0,sizeof(low)) ;memset(vis,0,sizeof(vis)) ;memset(in,0,sizeof(in)) ;memset(belong,0,sizeof(belong)) ;memset(sum,0,sizeof(sum)) ;while( !sta.empty() ) sta.pop() ;}void add(int u,int v){edge[cnt].u = u ;edge[cnt].v = v ;edge[cnt].next = head[u] ;head[u] = cnt++ ;}void add_tree(int u,int v){tree[cnt].u = u ;tree[cnt].v = v ;tree[cnt].next = h_tree[u] ;h_tree[u] = cnt++ ;}void tarjan(int u){dnf[u] = low[u] = ++time ;sta.push(u) ;vis[u] = 1 ;int i , v , j ;for(i = head[u] ; i != -1 ; i = edge[i].next){v = edge[i].v ;if( !dnf[v] ){tarjan(v) ;low[u] = min(low[u],low[v]) ;}else if( vis[v] ){low[u] = min(low[u],dnf[v]) ;}}if( low[u] == dnf[u] ){++num ;while( 1 ){j = sta.top() ;sta.pop() ;vis[j] = 0 ;belong[j] = num ;sum[num]++ ;if( j == u ) break ;}}}int main(){int n , m , ans ;int u , v , i , j ;while( scanf("%d %d", &n, &m) != EOF ){init() ;ans = 0 ;while( m– ){scanf("%d %d", &u, &v) ;add(u,v) ;}for(i = 1 ; i <= n ; i++)if( !dnf[i] ) tarjan(i) ;memset(in,0,sizeof(in)) ;for(i = 1 ; i <= n ; i++){for(j = head[i] ; j != -1 ; j = edge[j].next){u = belong[ edge[j].u ] ;v = belong[ edge[j].v ] ;if( u != v )in[u]++ ;}}for(i = 1 ; i <= num ; i++)if( in[i] == 0 ){ans += sum[i] ;sum[0]++ ;}if( sum[0] == 1 )printf("%d\n", ans) ;elseprintf("0\n") ;}return 0 ;}
勇敢的冷静的理智的去接受失败，有时不但是必要的，而且是很有必要的。
