【tarjan缩点】受欢迎的牛

P2341 [HAOI2006]受欢迎的牛

缩点令我快乐哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈

一遍过编译一遍A哈哈哈哈哈哈开心快乐哈哈哈哈哈哈哈哈哈哈

好吧其实很简单

因为牛的爱慕具有传递性（爱牛及牛？？

所以出度为0的强连通分量内牛的个数即为答案，但如果存在两个及两个以上的出度为0的强连通分量， ans = 0，因为这些强连通之间不连通qaq

差不多就是这样啦

noip2018 加油ヾ(◍°∇°◍)ﾉﾞ

 1 #include<cstdio>
 2 #include<iostream>
 3 #define ri register int
 4 #define ll long long
 5 #define maxn 10010
 6 #define maxm 50050
 7 using namespace std;
 8 int n, m, num = 0, top = 0, tim = 0, cnt = 0, num2 = 0;
 9 int node[maxn], head[maxm], head2[maxm],sd[maxn], chu[maxn], sta[maxn], low[maxn], dfn[maxn], x[maxm], y[maxm];
10 bool vis[maxn];
11 struct Edge {
12     int nxt, to;
13 }e[maxn << 1], edge[maxm << 1];
14 int read() {
15     char ch = getchar(); int x = 0, f = 1;
16     while(ch > '9' || ch < '0') {if(ch == '-') f = -1; ch = getchar();}
17     while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0' ; ch = getchar();}
18     return x * f;
19 }
20 void add(int from, int to) {
21     e[++num].nxt = head[from];
22     e[num].to = to;
23     head[from] = num;
24 }
25 void readd(int from, int to) {
26     chu[from]++;
27     edge[++num2].nxt = head2[from];
28     edge[num2].to = to;
29     head2[from] = num2;
30 }
31 void tarjan(int x) {
32     low[x] = dfn[x] = ++tim;
33     sta[++top]  = x;
34     vis[x] = 1;
35     for(int i = head[x]; i; i = e[i].nxt) {
36         int v = e[i].to;
37         if(!dfn[v]) {
38             tarjan(v);
39             low[x] = min(low[x], low[v]);
40         }
41         else if(vis[v]) low[x] = min(low[x], dfn[v]);
42     }
43     if(dfn[x] == low[x]) {
44         cnt++;
45         while(x != sta[top+1]) {
46             sd[sta[top]] = cnt;
47             vis[sta[top]] = 0;
48             node[cnt]++;
49             top--;
50         }
51     }
52 }
53 void search() {
54     int flag = 0, ans = 0;
55     for(int i = 1; i <= cnt; i++) {
56         if(!chu[i]) {
57             if(!flag) {
58                 ans = node[i];
59                 flag = 1;
60             }
61             else {
62                 flag = 2;
63                 break;
64             }
65         }
66     }
67     if(flag == 1) {
68         printf("%d", ans);
69         return;
70     }
71     else {
72         printf("0");
73         return;
74     }
75 }
76 int main() {
77     scanf("%d%d", &n, &m);
78     for(ri i = 1; i <= m; i++) {
79         x[i] = read(), y[i] = read();
80         add(x[i], y[i]);
81     }
82     for(ri i = 1; i <= n; i++) 
83         if(!dfn[i]) tarjan(i);
84     for(ri i = 1; i <= m; i++) {
85         int u = sd[x[i]], v = sd[y[i]];
86         if(u != v) readd(u, v);
87     }
88     search();
89     return 0;
90 }