「Bzoj 1654」「Usaco2006 Jan」The Cow Prom 奶牛舞会 (Tarjan找强连通分量)

BZOJ 1654
Luogu 2863
from: USACO 2006 Jan Sliver(USACO刷题第2题)

tarjan找强连通分量，最后输出强连通分量保含节点个数$>=2$的强连通分量个数即可，几乎是模板题

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stack>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;

const int MAXN = 10000 + 5;

int n, m;
vector<int> G[MAXN];
stack<int> s;
int scc_num, scc_siz[MAXN], dn[MAXN], low[MAXN], vi[MAXN], tb;

void tarjan(int u) {
    low[u] = dn[u] = ++tb;
    s.push(u), vi[u] = -1;
    for (int i=0;i<G[u].size();i++) {
        int v = G[u][i];
        if (vi[v]==0) {
            tarjan(v);
            low[u] = min(low[u], low[v]);
        } else if (vi[v]==-1) low[u] = min(low[u], dn[v]);
    }
    if (low[u]==dn[u]) {
        int e;
        scc_num++;
        do {
            e = s.top(); s.pop();
            vi[e] = 1;
            scc_siz[scc_num]++;
        }while (e!=u);
    }
}
void clear() {
    tb = scc_num = 0;
    for (int i=1;i<=n;i++) {
        G[i].clear();
        vi[i] = dn[i] = low[i] = scc_siz[i] = 0;
    }
}
void init() {
    clear();
    for (int i=1;i<=m;i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        G[a].push_back(b);
    }
}
void solve() {
    int ans = 0;
    for (int i=1;i<=n;i++) if (!dn[i]) tarjan(i);
    for (int i=1;i<=scc_num;i++) if (scc_siz[i]>=2) ans++;
    printf("%d\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d%d", &n ,&m)==2&&n&&m) init(), solve();
    return 0;
}