poj 2186 (强连通缩点)

题意：有N只奶牛，奶牛有自己认为最受欢迎的奶牛。奶牛们的这种“认为”是单向可传递的，当A认为B最受欢迎(B不一定认为A最受欢迎)，且B认为C最受欢迎时，A一定也认为C最受欢迎。现在给出M对这样的“认为...”的关系，问有多少只奶牛被除其本身以外的所有奶牛关注。

思路：既然有单向传递关系，那么关系图可能就形成了环，一个环内的奶牛互相认为。如果把这些环用一个点代替的话，建反图，就成了一个有向无环图了，直接遍历求出入度为0的点有多少个子节点就可以了。

#include<stdio.h>#include<string.h>#include<stack>using namespace std;const int N=10010;int low[N],dfs[N],ans,idx,cont[N],head[N],num,indep[N],belong[N],sum;bool ins[N];stack<int>Q;struct edge{int st,ed,next;}e[N*10];void addedge(int x,int y){e[num].st=x;e[num].ed=y;e[num].next=head[x];head[x]=num++;}void Tarjan(int u)//缩点{int i,v;Q.push(u);ins[u]=1;low[u]=dfs[u]=idx++;for(i=head[u];i!=-1;i=e[i].next){v=e[i].ed;if(dfs[v]==-1){Tarjan(v);low[u]=low[u]>low[v]?low[v]:low[u];}else if(ins[v]==1)low[u]=low[u]>dfs[v]?dfs[v]:low[u];}if(dfs[u]==low[u]){do{v=Q.top();Q.pop();ins[v]=0;belong[v]=ans;cont[ans]++;}while(v!=u);ans++;}}int Dfs(int u){int i,v,temp=0;for(i=head[u];i!=-1;i=e[i].next){v=e[i].ed;temp+=Dfs(v);}return temp+cont[u];//子节点+自己环内的所有点}int main(){int i,n,m,x,y;while(scanf("%d%d",&n,&m)!=-1){memset(head,-1,sizeof(head));num=0;ans=idx=0;for(i=0;i<m;i++){scanf("%d%d",&x,&y);addedge(x,y);}memset(cont,0,sizeof(cont));memset(ins,0,sizeof(ins));memset(dfs,-1,sizeof(dfs));for(i=1;i<=n;i++){if(dfs[i]==-1)Tarjan(i);}memset(head,-1,sizeof(head));memset(indep,0,sizeof(indep));num=0;for(i=0;i<m;i++){x=belong[e[i].st];y=belong[e[i].ed];if(x==y)continue;addedge(y,x);//建反图indep[x]++;}sum=0;for(i=0;i<ans;i++){if(indep[i]==0)if(Dfs(i)==n)sum+=cont[i];}printf("%d\n",sum);}return 0;}