1051: [HAOI2006]受欢迎的牛

HansBug

发布于 2018-04-10 08:50:58

60700

代码可运行

文章被收录于专栏：HansBug's LabHansBug's Lab

运行总次数：0

代码可运行

1051: [HAOI2006]受欢迎的牛

Time Limit: 10 Sec Memory Limit: 162 MB

Submit: 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

Sample Output

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 var
 8    i,j,k,l,m,n,h,t,ans:longint;
 9    s,ss:array[0..100000] of boolean;
10    a:array[0..100000] of point;
11    c:array[0..100000,1..2] of longint;
12    f,b,low,dfn,d,e:array[0..100000] of longint;
13 function min(x,y:longint):longint;inline;
14          begin
15               if x<y then min:=x else min:=y;
16          end;
17 procedure add(x,y:longint);inline;
18           var p:point;
19           begin
20                new(p);
21                p^.g:=y;
22                p^.next:=a[x];
23                a[x]:=p;
24           end;
25 procedure tarjan(x:longint);
26           var i,j,k:longint;p:point;
27           begin
28                inc(h);
29                low[x]:=h;dfn[x]:=h;
30                inc(t);
31                ss[x]:=true;s[x]:=true;
32                f[t]:=x;
33                p:=a[x];
34                while p<>nil do
35                      begin
36                           if not(s[p^.g]) then
37                              begin
38                                   tarjan(p^.g);
39                                   low[x]:=min(low[x],low[p^.g]);
40                              end
41                           else if ss[p^.g] then low[x]:=min(low[x],dfn[p^.g]);
42                           p:=p^.next;
43                      end;
44                if low[x]=dfn[x] then
45                   begin
46                        inc(ans);
47                        while f[t+1]<>x do
48                              begin
49                                   ss[f[t]]:=false;
50                                   b[f[t]]:=ans;
51                                   dec(t);
52                              end;
53                   end;
54           end;
55 begin
56      readln(n,m);
57      fillchar(s,sizeof(s),0);
58      fillchar(ss,sizeof(ss),0);
59      fillchar(b,sizeof(b),0);
60      fillchar(low,sizeof(low),0);
61      fillchar(dfn,sizeof(dfn),0);
62      for i:=1 to n do a[i]:=nil;
63      for i:=1 to m do
64          begin
65               readln(c[i,1],c[i,2]);
66               add(c[i,1],c[i,2]);
67          end;
68      tarjan(1);
69      fillchar(d,sizeof(d),0);
70      fillchar(e,sizeof(e),0);
71      for i:=1 to n do inc(e[b[i]]);
72      for i:=1 to m do
73               if b[c[i,1]]<>b[c[i,2]] then inc(d[b[c[i,1]]]);   //吐槽：这边我第一遍交的时候写的是inc(d[c[i,1]])，显然这是一个相当愚蠢的错误，可问题是居然还是AC了？！？！表示不解*_*(HansBug:我猜是phile神犇保佑了吧233)
74      j:=-1;
75      for i:=1 to ans do
76          begin
77               if d[i]=0 then
78                  begin
79                       if j=-1 then j:=i else
80                          begin
81                               writeln(0);
82                               halt;
83                          end;
84                  end;
85          end;
86      if j=-1 then writeln(0) else writeln(e[j]);
87      readln;
88 end.
89