首页 > 代码库 > 1051: [HAOI2006]受欢迎的牛
1051: [HAOI2006]受欢迎的牛
1051: [HAOI2006]受欢迎的牛
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 2410 Solved: 1276
[Submit][Status]
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
Source
题解：这辈子第一次写tarjan强连通分量，才知道这玩意可以如此霸气地实现缩点。在这里面就是先缩完了点，然后重新弄出来一个图，然后看图上出度为0的点是否唯一，如果唯一，输出这个缩点上有多少个点，否则0.。。。么么哒（个人觉得百度百科的算法讲解说的挺好的，赞一个：传送门在此）
1 type 2 point=^node; 3 node=record 4 g:longint; 5 next:point; 6 end; 7 8 var 9 i,j,k,l,m,n,h,ans,t:longint;10 a:array[0..100000] of point;11 low,dfn,b,f,d,e:array[0..100000] of longint;12 c:array[0..100000,1..2] of longint;13 s,ss:array[0..100000] of boolean;14 procedure add(x,y:longint);inline;15 var p:point;16 begin17 new(p);18 p^.g:=y;19 p^.next:=a[x];20 a[x]:=p;21 end;22 function min(x,y:longint):longint;inline;23 begin24 if x<y then min:=x else min:=y;25 end;26 function max(x,y:longint):longint;inline;27 begin28 if x>y then max:=x else max:=y;29 end;30 31 procedure tarjan(x:longint);32 var33 i,j,k:longint;p:point;34 begin35 inc(h);36 dfn[x]:=h;37 low[x]:=h;38 inc(t);39 f[t]:=x;40 s[x]:=true;41 ss[x]:=true;42 p:=a[x];43 while p<>nil do44 begin45 i:=p^.g;46 if not s[i] then47 begin48 tarjan(i);49 low[x]:=min(low[x],low[i]);50 end51 else if ss[i] then low[x]:=min(low[x],dfn[i]);52 p:=p^.next;53 end;54 if dfn[x]=low[x] then55 begin56 inc(ans);57 while f[t+1]<>x do58 begin59 ss[f[t]]:=false;60 b[f[t]]:=ans;61 dec(t);62 end;63 end;64 end;65 begin66 fillchar(b,sizeof(b),0);67 fillchar(s,sizeof(s),false);68 fillchar(ss,sizeof(ss),false);69 readln(n,m);70 for i:=1 to n do a[i]:=nil;71 for i:=1 to m do72 begin73 readln(c[i,1],c[i,2]);74 add(c[i,1],c[i,2]);75 end;76 ans:=0;77 tarjan(1);78 for i:=1 to n do a[i]:=nil;79 fillchar(d,sizeof(d),0);80 fillchar(e,sizeof(e),0);81 for i:=1 to n do inc(e[b[i]]);82 for i:=1 to m do83 if b[c[i,1]]<>b[c[i,2]] then inc(d[c[i,1]]);84 j:=-1;85 for i:=1 to ans do86 begin87 if d[i]=0 then88 begin89 if j=-1 then j:=i else90 begin91 writeln(0);92 halt;93 end;94 end;95 end;96 if j=-1 then writeln(0) else writeln(e[j]);97 readln;98 end.99
1051: [HAOI2006]受欢迎的牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。