题面：[USACO03FALL] 受欢迎的牛 G

大秦为你打开题目传送门

题目背景

本题测试数据已修复。

题目描述

每头奶牛都梦想成为牛棚里的明星。被所有奶牛喜欢的奶牛就是一头明星奶牛。所有奶牛都是自恋狂，每头奶牛总是喜欢自己的。奶牛之间的“喜欢”是可以传递的——如果 $A$ 喜欢 $B$，$B$ 喜欢 $C$，那么 $A$ 也喜欢 $C$。牛栏里共有 $N$ 头奶牛，给定一些奶牛之间的爱慕关系，请你算出有多少头奶牛可以当明星。

输入格式

第一行：两个用空格分开的整数：$N$ 和 $M$。

接下来 $M$ 行：每行两个用空格分开的整数：$A$ 和 $B$，表示 $A$ 喜欢 $B$。

输出格式

一行单独一个整数，表示明星奶牛的数量。

样例 #1

样例输入 #1

1
2
3
4
3 3
1 2
2 1
2 3

样例输出 #1

1
1

提示

只有 $3$ 号奶牛可以做明星。

【数据范围】

对于 $10\%$ 的数据，$N\le20$，$M\le50$。

对于 $30\%$ 的数据，$N\le10^3$，$M\le2\times 10^4$。

对于 $70\%$ 的数据，$N\le5\times 10^3$，$M\le5\times 10^4$。

对于 $100\%$ 的数据，$1\le N\le10^4$，$1\le M\le5\times 10^4$。

思路

首先，显而易见的，这个奶牛的爱慕关系是一个有向图，并且显而易见会出现环，而环就代表了强连通，也就是说可以缩点，所点之后的 DAG 如果有一个点出度为 0 ，就说明他没有爱慕的奶牛了，那么他就是满足条件的。但是说这个点只能有一个，你想想，如果有多个点出度为 0 那么那些出度为 0 的一定得不到所有奶牛的爱慕。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int MaxV = 1e4 + 10;
const int MaxE = 5e4 + 10;

template<int N, int M>
class Graph {
    private :
        struct Edge {
            int to, nt, wt;
            Edge() {}
            Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
        }e[M];
        int hd[N], cnte;
    public :
        inline void clear() { memset(hd, 0, sizeof(hd)), cnte = 0; }
        inline void AddEdge(int u, int v, int w = 0) {
            e[++cnte] = Edge(v, hd[u], w);
            hd[u] = cnte;
        }
        inline int head(int u) { return hd[u]; }
        inline int nt(int u) { return e[u].nt; }
        inline int to(int u) { return e[u].to; }
        inline int wt(int u) { return e[u].wt; }
};

int n, m;
int uid[MaxE], vid[MaxE];
Graph< MaxV, MaxE >G;

inline void Input() {
    read(n, m);
    for(int i = 1; i <= m; i++) {
        read(uid[i], vid[i]);
        G.AddEdge(uid[i], vid[i]);
    }
}

int dfn[MaxV], low[MaxV], cntd;
stack<int >stk; int instk[MaxV];
int cntc, col[MaxV];
vector<int >clb[MaxV];

void Tarjan(int u) {
    dfn[u] = low[u] = ++cntd;
    stk.push(u), instk[u] = 1;
    for(int i = G.head(u); i; i = G.nt(i)) {
        int v = G.to(i);
        if(!dfn[v]) { 
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]) { 
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]) {
        ++cntc;
        int v = stk.top(); stk.pop();
        while(v != u) {
            col[v] = cntc;
            instk[v] = 0;
            clb[cntc].push_back(v);
            v = stk.top(); stk.pop();
        }
        col[v] = cntc;
        instk[v] = 0;
        clb[cntc].push_back(v);
    }
}

int otD[MaxV];

inline void Init() {
    for(int i = 1; i <= m; i++) {
        if(col[uid[i]] == col[vid[i]]) continue;
        otD[col[uid[i]]]++;
    }
}

inline void Work() {
    for(int i = 1; i <= n; i++) {
        if(dfn[i] == 0) {
            Tarjan(i);
        }
    }
    Init();
    // TopoSort();
    int ans = 0;
    for(int i = 1; i <= cntc; i++) {
        // cout << sz[i] << endl;
        if(otD[i] == 0) {
            if(ans != 0) {
                printf("0\n");
                return ;
            }
            ans = clb[i].size();
        }
    }
    printf("%d\n", ans);
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}