dfs森林

把每个点进行一个dfs，不重复访问同一个点，走过的树形结构

SCC

强联通：\(u\) 能到达 \(v\)，且 \(v\) 能走到 \(u\)

传递性：\(u\) 和 \(v\) 强联通，\(v\) 和 \(w\) 强联通，有 \(u\) 和 \(w\) 强联通

tarjan 算法

在dfs森林中，一个子树若向祖先连接一条边，那么说明在一个强联通分量内，否则自己是一个强联通分量；

不妨用 dfn 记录 dfs 的时间戳，用 low 数组记录子树中连接的最远祖先的编号，即：

• low[u] == dfn[u] 时，将 u 的子树的没被 scc 的点存入一个新的 scc
• low[u] != dfn[u] 时，说明存在向祖先的边，继续回溯

一个实现：

vector<vector<int>> gra;
vector<int> low, bel, vis, ins;
stack<int> sta;
int cnt, idx;

void dfs(int u) {
    vis[u] = 1;
    low[u] = idx++;
    int now = low[u];
    ins[u] = 1;
    sta.push(u);
    for (auto v : gra[u])
        if (!vis[v])
            dfs(v), low[u] = min(low[u], low[v]);
        else if (ins[v])
            low[u] = min(low[u], low[v]);
    if (low[u] == now) {
        while (1) {
            int x = sta.top();
            sta.pop();
            ins[x] = 0;
            bel[x] = cnt;
            if (x == u)
                break;
        }
        cnt++;
    }
}

kosaraju 算法

DAG(有向无环图) 的dfs出栈顺序是反图的拓扑序

scc的点在反图中还是个scc

scc中的点在返图中不向scc外连出边

而后序遍历序中

故在返图中倒着dfs即可找到scc

一个实现:

vector<vector<int>> gra[2], scc;
vector<int> vis, c, bel;
stack<int> sta;
int cnt;

void dfs1(int u) {
    vis[u] = 1;
    for (auto v : gra[0][u])
        if (!vis[v])
            dfs1(v);
    sta.push(u);
}

void dfs2(int u) {
    vis[u] = 1;
    bel[u] = cnt;
    c.push_back(u);
    for (auto v : gra[1][u])
        if (!vis[v])
            dfs2(v);
}

void solve() {
    int n, m;
    cin >> n >> m;
    gra[0].resize(n + 1), gra[1].resize(n + 1);
    bel.resize(n + 1);
    vis.resize(n + 1);
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        gra[0][u].push_back(v);
        gra[1][v].push_back(u);
    }
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs1(i);
    vis.assign(n + 1, 0);
    do {
        dfs2(sta.top());
        cnt++;
        sort(c.begin(),c.end());
        scc.push_back(std::move(c));
        c.clear();
        while (sta.size() && vis[sta.top()])
            sta.pop();
    } while (sta.size());
    sort(scc.begin(), scc.end());
    cout << scc.size() << endl;
    for (auto &i : scc) {
        for (auto j : i)
            cout << j << ' ';
        cout << endl;
    }
}

例题

板子题：

• B3609 [图论与代数结构 701] 强连通分量
• P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G

例题：

• P2272 [ZJOI2007] 最大半连通子图
• P3627 [APIO2009] 抢掠计划

删掉切边.(2024牛客多校6 D题)

#include <bits/stdc++.h>

#ifdef LOCAL
#include "debug.h"
#else
#define deb(...) 114514
#endif

using namespace std;

using LL = long long;
using pii = pair<int, int>;
using pll = pair<LL, LL>;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9 + 7;
const int N = 3e5 + 10;

class DSU {
public:
    std::vector<int> d;
    DSU(std::size_t size) : d(size + 1) {
        std::iota(d.begin(), d.end(), 0);
    }
    int root(int u) {
        return d[u] == u ? u : d[u] = root(d[u]);
    }
    void bind(int u, int v) {
        d[root(u)] = root(v);
    }
};

void solve() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> gra(n + 1);
    vector<array<int, 2>> edge;
    set<array<int, 2>> e;
    while (m--) {
        int u, v;
        string s;
        cin >> u >> v >> s;
        if (s[0] == 'L') {
            gra[u].push_back(v);
            gra[v].push_back(u);
            e.insert({u, v});
        } else
            edge.push_back({u, v});
    }
    DSU dsu(n);
    vector<int> vis(n + 1);
    vector<int> ins(n + 1);
    vector<int> low(n + 1);
    stack<int> sta;
    int idx = 0;
    auto dfs = [&](int x, int pre, auto self) -> void {
        int dfn = low[x] = idx++;
        sta.push(x);
        vis[x] = 1;
        for (auto v : gra[x]) {
            if (!vis[v])
                self(v, x, self);
            if (pre == v)
                continue;
            low[x] = min(low[x], low[v]);
        }
        deb(x, dfn, low[x]);
        deb(ins);
        if (low[x] != dfn)
            ins[x] = 1;
        for (auto v : gra[x])
            if (v != pre && !ins[v] && low[v] > dfn) {
                deb(v, x);
                e.erase({v, x}), e.erase({x, v});
            }
        // ins[x] = 1;
    };
    for (int i = 1; i <= n; i++) {
        if (!vis[i])
            dfs(i, 0, dfs);
    }
    deb(e);
    for (auto [x, y] : e) dsu.bind(x, y);
    for (auto [x, y] : edge) {
        if (dsu.root(x) != dsu.root(y))
            dsu.bind(x, y), e.insert({x, y});
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (dsu.root(i) == i)
            cnt++;
    }
    if (cnt >= 2)
        cout << "NO" << '\n';
    else {
        cout << "YES" << '\n';
        cout << e.size() << '\n';
        for (auto [x, y] : e) cout << x << ' ' << y << '\n';
    }
}

signed
main() {
#ifdef LOCAL
    clock_t tttttttt = clock();
    freopen("in.txt", "r", stdin);
#endif
#ifndef LOCAL
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#endif
    //*****************************************************************
    int t = 1;
    // cin >> t;
    while (t--) solve();
//*****************************************************************
#ifdef LOCAL
    cerr << "Time Used: " << fixed << setprecision(3) << (clock() - tttttttt) / (CLOCKS_PER_SEC / 1000.0) << " ms" << endl;
#endif
    return 0;
}