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
Solution
用Tarjan强联通缩点即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 |
#include<iostream> #include<cstdio> using namespace std; const int N=10010,M=50010; int n,m,tot,cnt,top,number,u[M],v[M],Next[M],head[N],tree[M],stack[N],dfn[N]; int low[N],belong[N],size[N],chu[N]; bool ins[N]; void add(int x,int y) { tot++; Next[tot]=head[x]; head[x]=tot; tree[tot]=y; } void Tarjan(int u) { stack[++top]=u;ins[u]=true; dfn[u]=low[u]=++cnt; for (int i=head[u];i;i=Next[i]) { int v=tree[i]; if (dfn[v]==0) { Tarjan(v);low[u]=min(low[u],low[v]);} else low[u]=min(dfn[v],low[u]); } int i; if (low[u]==dfn[u]) { number++; do { i=stack[top--]; ins[i]=false; belong[i]=number; size[number]++; }while (i!=u); } } int main() { scanf("%d%d",&n,&m); tot=cnt=top=number=0; for (int i=1;i<=m;i++) { scanf("%d%d",&u[i],&v[i]); add(u[i],v[i]); } for (int i=1;i<=n;i++) if (dfn[i]==0) Tarjan(i); for (int i=1;i<=m;i++) if (belong[u[i]]!=belong[v[i]]) chu[belong[u[i]]]++; int flag=0; for (int i=1;i<=number;i++) if (chu[i]==0) { if (flag!=0) { printf("0\n");return 0;} flag=i; } printf("%d\n",size[flag]); return 0; } |
跟紧大佬的步伐
2161744 yzdwg 1051 Accepted 4184 kb 132 ms C++/Edit 2824 B 2017-07-11 22:46:45