每一头牛的愿望就是变成一头最受欢迎的牛。现在有N头牛,给你M对整数(A,B),表示牛A认为牛B受欢迎。 这
种关系是具有传递性的,如果A认为B受欢迎,B认为C受欢迎,那么牛A也认为牛C受欢迎。你的任务是求出有多少头
牛被所有的牛认为是受欢迎的。
秘闯金三角,加油小毛虫歌词,butterfly的复数
一个数,即有多少头牛被所有的牛认为是受欢迎的。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstdio> 4 #include<cstdlib> 5 using namespace std; 6 7 const int maxn=50000+5; 8 9 struct node{ 10 int net; 11 int to; 12 int w; 13 }a[maxn*3]; 14 int head[maxn],dfn[maxn],low[maxn],sum,ans,st[maxn],top; 15 int du[maxn],dep,cnt,tmp,rs[maxn],x[maxn],y[maxn],em[maxn]; 16 bool vis[maxn]; 17 int n,m; 18 int tt; 19 20 inline void add(int x,int y) 21 { 22 a[++cnt].to=y; 23 a[cnt].net=head[x]; 24 head[x]=cnt; 25 } 26 27 void tarjan(int u) 28 { 29 ++dep; 30 low[u]=dfn[u]=dep; 31 st[++top]=u; 32 vis[u]=true; 33 for(int i=head[u];i;i=a[i].net) 34 { 35 int v=a[i].to; 36 if(!dfn[v]) 37 { 38 tarjan(v); 39 low[u]=min(low[u],low[v]); 40 } 41 else if(vis[v]) 42 { 43 low[u]=min(low[u],dfn[v]); 44 } 45 } 46 if(low[u]==dfn[u]) 47 { 48 int now; 49 sum++; 50 do 51 { 52 now=st[top--]; 53 rs[now]=sum; 54 vis[now]=0; 55 em[sum]++; 56 }while(now!=u); 57 } 58 } 59 60 int main() 61 { 62 scanf("%d%d",&n,&m); 63 for(int i=1;i<=m;i++) 64 { 65 scanf("%d%d",&x[i],&y[i]); 66 add(x[i],y[i]); 67 } 68 for(int i=1;i<=n;i++) 69 { 70 if(!dfn[i]) 71 { 72 tarjan(i); 73 } 74 } 75 for(int i=1;i<=n;i++) 76 { 77 for(int j=head[i];j;j=a[j].net) 78 { 79 int v=a[j].to; 80 if(rs[i]!=rs[v]) 81 { 82 du[rs[i]]++; 83 } 84 } 85 } 86 for(int i=1;i<=sum;i++) 87 if(!du[i]) 88 { 89 if(tt) 90 { 91 puts("0\n"); 92 return 0; 93 } 94 tt=i; 95 } 96 printf("%d\n",em[tt]); 97 return 0; 98 }
如对本文有疑问,请在下面进行留言讨论,广大热心网友会与你互动!! 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论