1051: [HAOI2006]受欢迎的牛

 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