写了好长时间。。。。才过得。
太不容易了
http://acm.pku.edu.cn/JudgeOnline/problem?id=2186
题目大意 ： 有一些牛，然后他们互相仰慕，为有向图，仰慕可传递， a仰慕b， b仰慕c，a就仰慕c，让你求
解被所有牛仰慕的牛的个数。(貌似要找大牛呢。。。。汗)
思路： 好多大牛在disduss
里面也说了，就是有向图的强连通分量，然后讲这个强连通分两压缩成一个点，这样，再重新构图，在新构的图中，找到出度为0的点，代表这个连同分量里面的点
不指向别的连同分量的点，也就是说，这些牛不仰慕别的牛。当然，如果这样的，出度为0的连同分两的点大于1，也就是重新生成的图不是连同的话，那么就代表
肯定不存在被所有牛都仰慕的牛了。
ps ：
上来搞了一把矩阵。。。然后wa。。。然后找报告。。。然后找到代码。。。然后rand数据。。。然后比较。。。最后竟然发现报告的程序有bug。。。。
瀑布汗。。。。。最后感觉改的没问题了。。。交。。。。mle。。。。瞬间崩塌。。。。早晨起来接着搞。。。。最后链存过的。。。。。
方法 ： 求解连同分量正dfs，求解后续遍历序号，按序号从大到小dfs原图的逆图。这样，能求找到每个点属于哪个连同分量。 然后就一顿乱gao。。。时间复杂度巨高。。。。
1 #include <stdio.h>
2 #include <string.h>
3 #define max 10001
4 using namespace std;
5 int m, n, judge[max], back[max], backnum, tback[max], degree[max], belon[max];
6 struct P{
7 int v;
8 P* next;
9 };
10 void zdfs(int u, P** map){
11 int i;
12 judge[u] = 1;
13 P* p = map[u];
14 while(p){
15 if(!judge[p->v])
16 zdfs(p->v, map);
17 p = p->next;
18 }
19 back[u] = ++backnum;
20 }
21 void fdfs(int u, P** tmap, int d){
22 int i;
23 P* p = tmap[u];
24 belon[u] = d;
25 judge[u] = 1;
26 while(p){
27 if(!judge[p->v])
28 fdfs(p->v, tmap, d);
29 p = p->next;
30 }
31 }
32 void fengle(P** map, P** tmap){
33 int i, j, kn = 0, u, v, wrong = 0, ele = 0, res = 0;P* p;
34 for(i = 1; i <= m; i++){
35 if(!judge[i])
36 zdfs(i, map);
37 }
38 for(i = 1; i <= m; i++)
39 tback[back[i]] = i;
40 memset(judge, 0, sizeof(judge));
41 for(i = m, j = 1; i >= 1; i--){
42 if(!judge[tback[i]]){
43 fdfs(tback[i], tmap, j++);
44 kn++;
45 }
46 }
47 for(u = 1; u <= m; u++){
48 p = map[u];
49 while(p){
50 v = p -> v;
51 if(belon[u] != belon[v])
52 degree[belon[u]]++;
53 p = p->next;
54 }
55 }
56 for(i = 1; i <= kn; i++){
57 if(!degree[i]){
58 wrong++;
59 ele = i;
60 }
61 }
62 if(wrong > 1){
63 printf("0\n");return;
64 }
65 for(i = 1; i <= m; i++)
66 if(belon[i] == ele)
67 res++;
68 printf("%d\n", res);
69 }
70 int main(){
71 int i, j, u, v;
72 while(scanf("%d%d", &m, &n) != -1){
73 P* map[max];P* tmap[max];P* l;P* t;
74 memset(judge, 0, sizeof(judge));
75 memset(degree, 0, sizeof(degree));
76 backnum = 0;
77 for(i = 1; i < max; i++)
78 map[i] = tmap[i] = NULL;
79 for(i = 0; i < n; i++){
80 scanf("%d%d", &u, &v);
81 l = new P; //正图
82 l->v = v;
83 l->next = map[u];
84 map[u] = l;
85 l = new P; //反图
86 l->v = u;
87 l->next = tmap[v];
88 tmap[v] = l;
89 }
90 fengle(map, tmap);
91 for(i = 1; i <= m; i++){ //释放
92 l = map[i];
93 while(map[i]){
94 l = map[i];
95 map[i] = map[i]->next;
96 delete l;
97 }
98 }
99 for(i = 1; i <= m; i++){ //释放
100 l = tmap[i];
101 while(tmap[i]){
102 l = map[i];
103 tmap[i] = tmap[i]->next;
104 delete l;
105 }
106 }
107 }
108 return 0;
109 }