Submit: 7546 Solved: 4047
[Submit][Status][Discuss]
Description
每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这
种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
Input
第一行两个数N,M。 接下来M行,每行两个数A,B,意思是A认为B是受欢迎的(给出的信息有可能重复,即有可
能出现多个A,B)
Output
一个数,即有多少头牛被所有的牛认为是受欢迎的。
Sample Input
3 3
1 2
2 1
2 3
1 2
2 1
2 3
Sample Output
1
HINT
100%的数据N<=10000,M<=50000
Tarjan强连通分量
因为所有最受欢迎的牛,一定会互相欢迎最受欢迎的牛,所以所有最受欢迎的牛一定处在同一个强连通块中。
首先求出所有的强连通块,判断每条有向边是否属于不同的强连通块,如果属于不同的强连通块,则将发出这条边的强连通块的出度+1,(实际上就是将每个强连通块当作点来处理,也就是缩点)
最后判断是否存在出度为0的强连通块,如果只存在一个,则输出这个强连通块的数量。
如果存在多个则没有答案,输出0
1 #include<iostream> 2 #include<cstdio> 3 using namespace std; 4 5 const int MAXN=10000+5; 6 const int MAXM=50000+5; 7 struct Edge 8 { 9 int to,next; 10 }E[MAXM]; 11 int node,head[MAXM]; 12 int DFN[MAXN],LOW[MAXN],stack[MAXN]; 13 int vis[MAXN],size[MAXN],f[MAXN],num[MAXN]; 14 int index,top,tot,ans; 15 16 int n,m; 17 18 void insert(int u,int v) 19 { 20 E[++node]=(Edge){v,head[u]};head[u]=node; 21 } 22 23 void tarjan(int x) 24 { 25 DFN[x]=LOW[x]=++index; 26 stack[++top]=x; 27 vis[x]=1; 28 for(int i=head[x];i;i=E[i].next) 29 { 30 if(!DFN[E[i].to]) 31 { 32 tarjan(E[i].to); 33 LOW[x]=min(LOW[x],LOW[E[i].to]); 34 } 35 else if(vis[E[i].to]) 36 LOW[x]=min(LOW[x],DFN[E[i].to]); 37 } 38 int now; 39 if(LOW[x]==DFN[x]) 40 { 41 tot++; 42 do 43 { 44 now=stack[top--]; 45 size[tot]++; 46 f[now]=tot; 47 vis[now]=0; 48 }while(x!=now); 49 } 50 } 51 52 int main() 53 { 54 scanf("%d %d",&n,&m); 55 for(int i=1;i<=m;i++) 56 { 57 int a,b; 58 scanf("%d %d",&a,&b); 59 insert(a,b); 60 } 61 for(int i=1;i<=n;i++) 62 if(!DFN[i]) tarjan(i); 63 for(int i=1;i<=n;i++) 64 for(int j=head[i];j;j=E[j].next) 65 if(f[i]!=f[E[j].to]) 66 num[f[i]]++; 67 for(int i=1;i<=tot;i++) 68 if(!num[i]) 69 { 70 if(ans)//不允许出现第二个出度为0的强联通块 71 { 72 printf("0\n"); 73 return 0; 74 } 75 ans=i; 76 } 77 printf("%d\n",size[ans]); 78 return 0; 79 }