不知咋搞的,测试点红红绿绿啊
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
int n, m;
int b, e;
int dfn[100010], low[100010], _index;
int vis[100010], stk[100010];
int belong[100010], need[100010];
int tot, ans;
stack<int> s;
vector<int> g[100010];
void tarjan(int u) {
dfn[u] = low[u] == ++_index;
s.push(u);
vis[u] = stk[u] = 1;
int sum = g[u].size();
for (int i = 0; i < sum; ++i) {
int v = g[u][i];
if (!vis[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else {
if (stk[v]) {
low[u] = min(low[u], dfn[v]);
}
}
}
if (dfn[u] == low[u]) {
int v;
tot++;
do {
v = s.top();
stk[v] = 0;
belong[v] = tot;
s.pop();
} while (v != u);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; ++i) {
scanf("%d%d", &b, &e);
g[b].push_back(e);
}
for (int i = 1; i <= n; ++i) {
if (!vis[i]) {
tarjan(i);
}
}
for (int i = 1; i <= n; ++i) {
int sum = g[i].size();
for (int j = 0; j < sum; ++j) {
int x = g[i][j];
if (belong[i] != belong[x]) {
need[belong[x]] = 1;
}
}
}
for (int i = 1; i <= tot; ++i) {
if (!need[i]) {
ans++;
}
}
printf("%d\n", ans);
return 0;
}
没有A这题的蒟蒻,或者还有?
救救蒟蒻……