P2863 The Cow Prom S - 洛谷

P2863 [USACO06JAN] The Cow Prom S - 洛谷

题目描述

有一个 $n$ 个点，$m$ 条边的有向图，请求出这个图点数大于 $1$ 的强连通分量个数。

输入格式

第一行为两个整数 $n$ 和 $m$。

第二行至 $m+1$ 行，每一行有两个整数 $a$ 和 $b$，表示有一条从 $a$ 到 $b$ 的有向边。

数据范围： $2\le n\le {10}^4$，$2\le m\le 5\times {10}^4$，$1\le a,b\le n$。

输出格式

仅一行，表示点数大于 $1$ 的强连通分量个数。

样例 #1

样例输入 #1

5 4
2 4
3 5
1 2
4 1

样例输出 #1

1

董晓的模板直接用没有问题。oiwiki 的模板是链式前向星的模板，这个题还是邻接表更简单易懂一些。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
int n, m;
vector<int> e[N];
int dfn[N], low[N], tot;
int stk[N], instk[N], top;
int scc[N], siz[N], cnt;
void tarjan(int x)
{
    dfn[x] = low[x] = ++tot;
    stk[++top] = x;
    instk[x] = 1;

    for (int y : e[x]) //邻接表存图
    {
        if (!dfn[y])
            tarjan(y), low[x] = min(low[x], low[y]);
        else if (instk[y])
            low[x] = min(low[x], low[y]);
    }

    if (dfn[x] == low[x])
    {
        int y;
        ++cnt;
        do
        {
            y = stk[top--];
            instk[y] = 0;
            scc[y] = cnt;
            ++siz[cnt];
        } while (y != x);
    }
}
int main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b); //邻接表存图
    }
    for (int i = 1; i <= n; i++)
    {
        if (!instk[i])
            tarjan(i);
    }

    int count = 0;
    for (int i = 1; i <= cnt; i++)
    {
        if (siz[i] > 1)
            count++;
    }
    cout << count << '\n';
}