rt,我 tarjan 板子都错了,依然AC。
如下第 22 行,ins[v]
写成了 ins[u]
#include <bits/stdc++.h>
using namespace std;
const int M = 5e4 + 5;
const int N = 1e4 + 5;
int n, m;
vector<int> e[N];
int dfn[N], low[N], tim, Stack[N], top, belong[N], siz[N], fu[M], fv[M], dout[N];
bool ins[N];
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++tim;
Stack[++top] = u;
ins[u] = 1;
for(int v : e[u]) {
if(!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
}
else if(ins[u]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
while(Stack[top + 1] != u) {
siz[u]++;
belong[Stack[top]] = u;
ins[Stack[top--]] = 0;
}
}
}
void shrink_node() {
for(int i = 1; i <= m; ++i) {
int du = belong[fu[i]], dv = belong[fv[i]];
if(du != dv)
dout[du]++;
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i) {
cin >> fu[i] >> fv[i];
e[fu[i]].push_back(fv[i]);
}
for(int i = 1; i <= n; ++i) {
if(!dfn[i]) {
top = 0;
tarjan(i, 0);
}
}
shrink_node();
int cnt = 0, ans;
for(int i = 1; i <= n; ++i) {
if(dout[i] == 0 && belong[i] == i) {
cnt++;
ans = siz[i];
}
}
if(cnt == 1) cout << ans;
else cout << 0;
return 0;
}