CSES 1685：New Flight Routes

CSES 1685：New Flight Routes

題目大意：給你一張有向圖，請你加最少的邊使整張圖任一點均可到達另一點，並輸出加的邊。

解法：維基有說明。我們可以先跑一次 $\text{Tarjan}$，使整張圖變成以強連通分量為點的 $\text{DAG}$，而入度為 $0$ 的點加入集合 $S$，出度為 $0$ 的點加入集合 $T$，然後我們對每一個 $S$ 裡的點去找能不能到達 $T$ 裡的點 (且之前未被拜訪過)，將他們加入 $\text{match}$ 裡，而假設 $\text{match}$ 裡的第 $i$ 對為 $(s_i, t_i)$，我們將 $t_i$ 連到 $s_{i + 1}$，這樣就能形成一個環，把所有在 $\text{match}$ 裡的點形成一個 $\text{SCC}$。而未被匹配到的集合，假設為 $nS, nT$，那我們將 $nT_i$ 連到 $nS_i$，然後 $nS, nT$ 的大小可能不同，會有多出的，我們再用同一點與它們相連。這樣需要連邊的數量為 $\max(|S|, |T|)$。

$\text{Code：}$

#pragma GCC optimize("O3")
#pragma GCC target("popcnt")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define Waimai ios::sync_with_stdio(false),cin.tie(0)
#define FOR(x,a,b) for(int x=a;x<=b;x++)
#define pb emplace_back
#define F first
#define S second

const int SIZE = 1e5 + 5;

int n, m;
vector<int> adj[SIZE];
int dfcnt, sccnt;
int dfn[SIZE], low[SIZE], scc[SIZE], id[SIZE];
vector<int> st;
bool ist[SIZE];
vector<int> scc_adj[SIZE], vS, vT;
vector<pair<int, int>> ans, match;
bool vs[SIZE], isS[SIZE], isT[SIZE], ism[SIZE];

int dfs (int pos) {
    vs[pos] = 1;
    if (isT[pos]) return pos;
    for (int np : scc_adj[pos]) {
        if (vs[np]) continue;
        int re = dfs (np);
        if (re) return re;
    }
    return 0;
}

void tarjan (int pos) {
    dfn[pos] = low[pos] = ++dfcnt;
    st.pb (pos), ist[pos] = 1;
    for (int np : adj[pos]) {
        if (!dfn[np]) {
            tarjan (np);
            low[pos] = min (low[pos], low[np]);
        } else if (ist[np]) {
            low[pos] = min (low[pos], dfn[np]);
        }
    }
    if (low[pos] == dfn[pos]) {
        sccnt++;
        id[sccnt] = pos;
        while (1) {
            int x = st.back();
            ist[x] = 0;
            scc[x] = sccnt;
            st.pop_back();
            if (x == pos) break;
        }
    }
}

void solve() {
    cin >> n >> m;
    while (m--) {
        int a, b;
        cin >> a >> b;
        adj[a].pb (b);
    }
    FOR (i, 1, n) if (!dfn[i]) tarjan (i);
    if (sccnt == 1) {cout << "0\n"; return;}
    fill (isS + 1, isS + sccnt + 1, 1);
    FOR (i, 1, n) for (int j : adj[i]) if (scc[i] != scc[j]) {
        isS[scc[j]] = 0;
        scc_adj[scc[i]].pb (scc[j]);
    }
    n = sccnt;
    FOR (i, 1, n) isT[i] = scc_adj[i].size() == 0;
    int mS, mT;
    FOR (i, 1, n) if (isS[i] && ism[i] == 0) {
        int to = dfs (i);
        if (to) {
            match.pb (i, to);
            ism[i] = ism[to] = 1;
            mS = i, mT = to;
        }
    }
    for (int i = 0; i < match.size(); i++) ans.pb (id[match[i].S], id[match[(i + 1) % match.size()].F]);
    FOR (i, 1, n) {
        if (isS[i] && ism[i] == 0) vS.pb (i);
        if (isT[i] && ism[i] == 0) vT.pb (i);
    }
    for (int i = 0; i < min (vS.size(), vT.size()); i++) ans.pb (id[vT[i]], id[vS[i]]);
    if (vS.size() < vT.size()) {
        for (int i = vS.size(); i < vT.size(); i++) ans.pb (id[vT[i]], id[mS]);
    } else {
        for (int i = vT.size(); i < vS.size(); i++) ans.pb (id[mT], id[vS[i]]);
    }
    cout << ans.size() << '\n';
    for (auto [x, y] : ans) cout << x << ' ' << y << '\n';
}

int main() {
    Waimai;
    solve();
}

我的分享就到這裡結束了，如果喜歡我的 $\text{Blog}$，歡迎追蹤！