「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;
}

------ 本文结束 ------