POJ-2186-Popular Cows（Tarjan强联通，缩点）

题目链接：http://poj.org/problem?id=2186

题目大意：给出n个点m条边，组成一个有向图。定义a->b表示a崇拜b，a崇拜b，b崇拜c，那么a也崇拜c。

我们要找出有多少个人，被除了本身外所有的人崇拜。输出个数。

思路：找出这个图的强联通分量，同一个强联通分量的所有点都可以互相崇拜。那么我们就找出度为0的强联通分量就行了，如果个数>1说明答案是0，否则输出那个强联通分量内的所有人。

ACCode：

// luogu-judger-enable-o2
//#pragma comment(linker, "/STACK:1024000000,1024000000")
 
#include<stdio.h>
#include<string.h>
#include<math.h>
 
#include<map>
#include<set>
#include<deque>
#include<queue>
#include<stack>
#include<bitset>
#include<string>
#include<fstream>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define ll long long
#define Pair pair<int,int>
//#define max(a,b) (a)>(b)?(a):(b)
//#define min(a,b) (a)<(b)?(a):(b)
#define clean(a,b) memset(a,b,sizeof(a))// 水印
//std::ios::sync_with_stdio(false);
//  register
const int MAXN=1e4+10;
const int INF32=0x3f3f3f3f;
const ll INF64=0x3f3f3f3f3f3f3f3f;
const int MOD=1e9+7;
const double EPS=1.0e-8;
const double PI=acos(-1.0);

struct Node{
	int v,val,nxt;
	Node(int _v=0,int _val=0,int _nxt=0){
		v=_v;val=_val;nxt=_nxt;
	}
};
Node Edge[MAXN<<4];
int Head[MAXN],Ecnt;
int Dfn[MAXN],Low[MAXN],tot;
int Stk[MAXN],InStk[MAXN],Top;
int Belong[MAXN];
int OutDeg[MAXN];
int Ans[MAXN];
int Cnt;
int n,m;

void Intt(){
	clean(Head,-1);Ecnt=0;
	clean(Dfn,0);clean(Low,0);tot=0;
	clean(InStk,0);Top=0;
	clean(Belong,0);Cnt=0;
	clean(OutDeg,0);
}
void Add(int u,int v,int val){
	Edge[Ecnt]=Node(v,val,Head[u]);
	Head[u]=Ecnt++;
}
void Tarjan(int u){
	Dfn[u]=Low[u]=++tot;
	Stk[++Top]=u;
	InStk[u]=1;
	for(int i=Head[u];i+1;i=Edge[i].nxt){
		int temp=Edge[i].v;
		if(Dfn[temp]==0){
			Tarjan(temp);
			Low[u]=min(Low[u],Low[temp]);
		}
		else if(InStk[temp]){
			Low[u]=min(Low[u],Low[temp]);
		}
	}
	if(Dfn[u]==Low[u]){
		++Cnt;
		int temp;
		while(Stk[Top]!=u){
			temp=Stk[Top--];
			Belong[temp]=Cnt;
			InStk[temp]=0;
		}
		temp=Stk[Top--];
		Belong[temp]=Cnt;
		InStk[temp]=0;
	}
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		Intt();
		for(int i=1;i<=m;++i){
			int a,b;scanf("%d%d",&a,&b);
			Add(a,b,1);
		}
		for(int i=1;i<=n;++i){
			if(Dfn[i]==0){
				Tarjan(i);
			}
		}
//		for(int i=1;i<=n;++i) printf("%d %d\n",Dfn[i],Low[i]);
//		for(int i=1;i<=n;++i) printf("%d:%d  ",i,Belong[i]);printf("\n");
		for(int i=1;i<=n;++i){
			for(int j=Head[i];j+1;j=Edge[j].nxt){
				int temp=Edge[j].v;
				if(Belong[i]!=Belong[temp]){//i => temp
					OutDeg[Belong[i]]++;
				}
			}
		}
//		for(int i=1;i<=n;++i) printf("%d:%d  ",i,Belong[i]);printf("\n");
//		for(int i=1;i<=Cnt;++i){
//			printf("Kind = %d %d: ",i,OutDeg[i]);
//			for(int j=1;j<=n;++j){
//				if(Belong[j]==i) printf("%d ",j);
//			}printf("\n");
//		}
		int flag=-1;
		for(int i=1;i<=Cnt;++i){
			if(OutDeg[i]==0){
				if(flag==-1) flag=i;
				else{
					flag=-1;break;
				}
			}
		}
		if(flag==-1) printf("0\n");
		else{
			int ans=0;
			for(int i=1;i<=n;++i){
				if(Belong[i]==flag) ans++;
			}printf("%d\n",ans);
		}
	}
	
}

/*


5 6

1 2
2 1
2 3
2 4
4 5
5 4


*/