题目大意：有n头牛与m对关系，表示A牛仰慕B牛，如果A牛仰慕B牛，B牛仰慕C牛，那么我们可以认为A牛仰慕C牛，给出牛的数量与仰慕关系，求有多少牛被全部的牛仰慕。
解法：用普通的dfs无能为力，因为有环的存在，各种麻烦，于是用求强连通分量的算法，这里我用了kosaraju，将强连通分量求出来之后，据fjy的说法，不用实际缩点，是要用意念把点缩在一起，每个颜色只走一次（说一下缩点，截止2011.11.25为止，我还没做缩点），然后翻老程序中又翻出了一个更神的做法，如果有两个或以上颜色点没有指向其他颜色点的边，则说明无解，不然有解（因为说明有一些牛没有支持另外那部分的牛，只有一个说明全部的牛都指向了这个点！
{缩点不是真缩，置颜色枚举一次，kosaraju的拓扑性挺好的}
View Code
1 {usaco popular
2 }
3 const
4 maxn=10000;
5 maxm=50000;
6 type
7 data=record
8 dest, next: longint;
9 end;
10 var
11 edge, idol: array[1..maxm]of data;
12 wmz, stu, col, vect, turn: array[1..maxn]of longint;
13 visit: array[1..maxn]of boolean;
14 ans, p, tot, idt, color, n, m: longint;
15 procedure add(x, y: longint);
16 begin
17 inc(tot);
18 with edge[tot] do
19 begin
20 dest := y;
21 next := vect[x];
22 vect[x] := tot;
23 end;
24 end;
25
26 procedure dda(x, y: longint);
27 begin
28 inc(idt);
29 with idol[idt] do
30 begin
31 dest := y;
32 next := turn[x];
33 turn[x] := idt;
34 end;
35 end;
36
37 procedure init;
38 var
39 i, x, y: longint;
40 begin
41 fillchar(col, sizeof(col), 0);
42 fillchar(vect, sizeof(vect), 0);
43 fillchar(turn, sizeof(turn), 0);
44 fillchar(wmz, sizeof(wmz), 0);
45 tot := 0;
46 idt := 0;
47
48 readln(n, m);
49 for i := 1 to m do
50 begin
51 readln(x, y);
52 add(x, y);
53 dda(y, x);
54 end;
55 end;
56
57 procedure endtime(x: longint);
58 var
59 i: longint;
60 begin
61 visit[x] := true;
62 i := vect[x];
63 while i<>0 do
64 with edge[i] do
65 begin
66 if not visit[dest] then endtime(dest);
67 i := next;
68 end;
69 inc(p);
70 stu[p] := x;
71 end;
72
73 procedure dfs(x: longint);
74 var
75 i: longint;
76 begin
77 col[x] := color;
78 inc(wmz[color]);
79 i := turn[x];
80 while i<>0 do
81 with idol[i] do
82 begin
83 if col[dest]=0 then dfs(dest);
84 i := next;
85 end;
86 end;
87
88 procedure main;
89 var
90 i, j, u: longint;
91 begin
92 p := 0;
93 for i := 1 to n do
94 if not visit[i] then
95 endtime(i);
96 color := 0;
97 for i := n downto 1 do
98 if col[stu[i]]=0 then
99 begin
100 ans := 0;
101 inc(color);
102 dfs(stu[i]);
103 end;
104 fillchar(visit, sizeof(visit), 0);
105 for u := 1 to n do
106 begin
107 i := vect[u];
108 while i<>0 do
109 with edge[i] do
110 begin
111 if col[dest]<>col[u] then
112 visit[col[u]] := true;
113 i := next;
114 end;
115 end;
116 end;
117
118 procedure print;
119 var
120 i, s: longint;
121 begin
122 s := 0;
123 for i := 1 to color do
124 begin
125 if not visit[i] then
126 begin
127 if s=0 then s := i
128 else
129 begin
130 writeln(0);
131 exit;
132 end;
133 end;
134 end;
135 if s<>0 then writeln(wmz[s])
136 else writeln(0);
137 end;
138
139 begin
140 assign(input,'popular.in'); reset(input);
141 assign(output,'popular.out'); rewrite(output);
142
143 init;
144 main;
145 print;
146
147 close(input); close(output);
148 end.