POJ 3180

3180.cpp

#include <cstdio>
#include <cassert>
#include <vector>
using namespace std;

int ans;
int n;
int m;
int t;
bool used[10000];
int order[10000];
int belong[10000];
vector<int> es[10000];
vector<int> reves[10000];

void dfs(int v, int &id) {
    used[v] = true;

    for (int i=0; i<es[v].size(); i++) {
        int u = es[v][i];
        
        if (!used[u]) dfs(u, id);
    }

    order[id++] = v;
}

int rdfs(int v, int grp) {
    int num = 0;

    used[v] = true;
    belong[v] = grp;

    for (int i=0; i<reves[v].size(); i++) {
        int u = reves[v][i];

        if (!used[u]) num += rdfs(u, grp);
    }

    return num+1;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i=0; i<m; i++) {
        int a, b;

        scanf("%d%d", &a, &b);
        --a;
        --b;
        es[a].push_back(b);
        reves[b].push_back(a);
    }

    t = 0;
    for (int i=0; i<n; i++) {
        if (!used[i]) dfs(i, t);
    }

    fill(used, used+n, false);
    assert(t == n);
    t = 0;
    for (int i=n-1; i>=0; i--) {
        int v = order[i];

        if (!used[v]) {
            if (rdfs(v, t++) > 1) ans++;
        }
    }

    printf("%d\n", ans);
}