POJ 3180
题目大意
暂无
题目解法
暂无
RTFC
#include <cstdio>
inline int min(int a, int b) { return a < b ? a : b; }
const int maxn = 100010;
int head[maxn], next[maxn << 1], to[maxn << 1], ecnt, n, m;
int dfn[maxn], scc[maxn], cnt[maxn], scccnt, stk[maxn], low[maxn], idx, top;
inline void addEdge(int f, int t)
{
ecnt++;
next[ecnt] = head[f];
head[f] = ecnt;
to[ecnt] = t;
}
void tarjan(int x)
{
dfn[x] = low[x] = ++idx;
stk[top++] = x;
for (int i = head[x]; i; i = next[i])
if (!dfn[to[i]])
tarjan(to[i]), low[x] = min(low[x], low[to[i]]);
else if (!scc[to[i]])
low[x] = min(low[x], dfn[to[i]]);
if (dfn[x] == low[x])
{
scccnt++;
do
scc[stk[--top]] = scccnt;
while (stk[top] != x);
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 0, x, y; i < m; i++)
{
scanf("%d%d", &x, &y);
addEdge(x, y);
}
for (int i = 1; i <= n; i++)
if (!dfn[i]) tarjan(i);
int ans = 0;
for (int i = 1; i <= n; i++) cnt[scc[i]]++;
for (int i = 1; i <= scccnt; i++)
if (cnt[i] > 1) ans++;
printf("%d", ans);
return 0;
}