WA 80
查看原帖
WA 80
1042486
larryia楼主2024/7/25 20:36
#include <bits/stdc++.h>
using namespace std;
const int M = 5e4 + 10;
const int N = 1e4 + 10;
int n, m, idx, h[N];
struct edge {
    int v, ne;
}e[M];
void init() {
    idx = 0;
    memset(h, -1, sizeof h);
}
void addEdge(int u, int v) {
    e[++idx] = (edge){v, h[u]};
    h[u] = idx;
}
int tot, siz[N], stk[N], instk[N], cnt, top;
int dfn[N], low[N];
void tarjan(int x) {
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;
    for (int i = h[x]; i != -1; i = e[i].ne) {
        int y = e[i].v;
        if (dfn[y] == 0) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (instk[y] == 1) {
            low[x] = min(low[x], dfn[y]);
        }
    }

    if (dfn[x] == low[x]) {
        cnt++;
        do {
            instk[top] = 0;
            siz[cnt]++;
        }
        while (x != stk[top--]);
    }
    if (siz[cnt] == 1) siz[cnt--] = 0;
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }
    
    for (int i = 1; i <= n; i++) {
        if (dfn[i]) continue;
        tarjan(i);
    }
    cout << cnt << endl;
    return 0;
}
2024/7/25 20:36
加载中...