前言

距离 2026 CSP 还有 2 天。

突然发现神犇的拼音首字母是 sb

---

$\textsf{拓扑排序}$

在有向无环图（DAG）中，一种点的排列顺序。对于每个点，所有在拓扑排序中指向它的点都在它之前。例如图：

一种合法的拓扑排序是：$1,3,2,4,5$。这样，指向 $5$ 的 $3,4$ 都在 $5$ 之前，指向 $3$ 的 $1$ 在 $3$ 之前，指向 $4$ 的 $2$ 在 $4$ 之前。当然拓扑排序不止一种。

$\text{BFS}$ 求拓扑排序

• 将所有入度为 $0$ 的点入队。
• 取出队头，遍历相连的点。
  • 取出相连的点，将入度减一。如果入度变为 $0$ 则入队。
• 直到队列为空。

$\text{Tarjan}$：割点

割点是无向图中的概念。

当去掉某个点后，图变成两个联通分量，则这个点就是割点。如图 $2,3$ 为割点。

Tarjan 求割点会需要定义两个数组：dfn[u] 和 low[u] 分别表示 $u$ 的 dfs 序和能返回的最小祖先的 dfs 序。

如上图进行 DFS 得到 DFS 树，并标出 dfn 和 low。一开始都是 dfs 序。

遍历 $3$ 时，发现 $3$ 与一个 dfn 更小的点 $1$ 相连。说明 $3$ 可以返回 $1$。那么更小 $3$ 的 low 为 $1$ 的 dfn 即 $1$。

此时发现 $6$ 的 low 即能返回的祖先中 dfn 最小的，都比某个祖宗 $3$ 的 dfn 要大。说明 $6$ 不可能返回 $3$ 以前的祖宗。那么此时 $3$ 就是割点。应为割掉 $3$ 之后 $6$ 也会被带走。

回溯到 $5$。$5$ 的子节点 $3$ 能回到 dfn 小于 $5$ 的 dfn 的节点，那么 $5$ 不是割点。

回溯到 $2$，发现 $4$ 和 $5$ 都不能回到 $2$ 以前的点。那么 $2$ 也是割点。

根节点特判

注意根节点不能用那样的方法判断。只有当 DFS 树中，根节点有 $2$ 个及以上的孩子时，根才为割点。

#include <vector>
#include <iostream>
using namespace std;

const int N = 2e4 + 5;
int n, m, cnt, dfn[N], low[N], root;
vector <int> g[N];
bool isc[N];

void dfs(int u, int fa)
{
    dfn[u] = low[u] = ++cnt;
    int cld = 0; // 孩子数量
    for (auto v : g[u])
    {
        if (v == fa) continue;
        if (!dfn[v])
        {
            ++cld;
            dfs(v, u);
            low[u] = min(low[u], low[v]);
            if (u != root && low[v] >= dfn[u])
                isc[u] = 1;
        }
        else low[u] = min(low[u], dfn[v]);
    }
    if (u == root && cld > 1)
        isc[u] = 1;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= n; ++i)
    {
        if (!dfn[i])
        {
            root = i;
            dfs(root, -1);
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        ans += isc[i];
    cout << ans << '\n';
    for (int i = 1; i <= n; ++i)
        if (isc[i]) cout << i << ' ';
    return 0;
}

$\text{Tarjan}$：缩点

缩点其实和割点很想。有一个区别。缩点用于有向图，缩点后，有向图会变为有向无环图（DAG），此时就可以用拓扑排序 + DP。

$low$ 相同的点就在一个缩点内。搜索时入栈。判断方法就在 dfs 末尾判断。如果 $dfn_u=low_u$，那么将栈顶弹出，直到 $u$。

洛谷模板。

Tarjan

// Tarjan / SCC
int Tjcnt, dfn[N], low[N];
int sccnt, scn[N]; // u 处于哪个 scn
int val[N]; // 第 i 个缩点的权值

bool ins[N]; // 是否在栈中
stack <int> sk;

// 拓扑排序 + DP
int idsc[N]; //第 i 个缩点的入度
int dp[N]; // 走到第 i 个 SCC 的最大权值

void dfs(int u)
{
    dfn[u] = low[u] = ++Tjcnt;
    sk.push(u); ins[u] = 1;
    for (int v : g[u])
    {
        if (!dfn[v])
        {
            dfs(v);
            low[u] = min(low[u], low[v]);
        }
        else if (ins[v])
            low[u] = min(low[u], dfn[v]);
    }

    if (dfn[u] == low[u])
    {    // SCC
        ++sccnt;
        while (sk.size() && sk.top() != u)
        {
            int v = sk.top();
            sk.pop(); ins[v] = 0;
            scn[v] = sccnt;
            val[sccnt] += a[v];
        }
        sk.pop(); ins[u] = 0;
        scn[u] = sccnt;
        val[sccnt] += a[u];
    }
}

缩点。

    // SCC
    for (int u = 1; u <= n; ++u)
    {
        for (int v : g[u])
        {
            if (scn[u] != scn[v])
                scg[scn[u]].push_back(scn[v]);
        }
    }
    for (int i = 1; i <= sccnt; ++i)
    {
        sort(scg[i].begin(), scg[i].end());
        scg[i].erase(unique(scg[i].begin(), scg[i].end()), scg[i].end());

        for (int v : scg[i])
            ++idsc[v];
    }

拓扑排序 + DP。

    // 拓扑排序
    queue <int> q;
    for (int i = 1; i <= sccnt; ++i)
    {
        dp[i] = val[i];
        if (idsc[i] == 0)
            q.push(i);
    }

    while (q.size())
    {
        int f = q.front();
        q.pop();

        for (int v : scg[f])
        {
            dp[v] = max(dp[v], dp[f] + val[v]);
            if (--idsc[v] == 0)
                q.push(v);
        }
    }

    // 答案
    int ans = 0;
    for (int i = 1; i <= sccnt; ++i)
        ans = max(ans, dp[i]);