โปรแกรม C++ หาจำนวนเส้นขอบสะพาน (Bridge Edges) ในกราฟ

กำหนดกราฟไม่มีทิศทาง ไม่มีน้ำหนัก n จุดยอด m เส้นขอบ (ไม่มีขอบขนานหรือลูป) "Bridge Edge" คือเส้นขอบที่ถ้าลบออกจะทำให้กราฟไม่เชื่อมต่อ (disconnected) ต้องการหาจำนวน Bridge Edges

ตัวอย่าง: n=5, m=6, edges={{1,2},{1,3},{2,3},{2,4},{2,5},{3,5}} ผลลัพธ์: 1 (เฉพาะขอบ {2,4} เป็นสะพาน)

ขั้นตอนการแก้ปัญหา (DFS + Low-link / Tarjan)

1. สร้างกราฟ G จาก edges
2. อาร์เรย์ visited, vk (เวลาเข้า), l (low-link), bridge 2D
3. DFS(v, p):
   • visited[v]=1, vk[v]=l[v]=t++
   • สำหรับเพื่อนบ้าน x:
     • ถ้า x==p ข้าม
     • ถ้า visited[x] อัปเดต l[v] = min(l[v], vk[x])
     • มิฉะนั้น DFS(x, v) แล้ว l[v] = min(l[v], l[x]) ถ้า l[x] > vk[v] → bridge[v][x] = 1
4. เรียก DFS สำหรับทุกคอมโพเนนต์ แล้วนับ bridge[i][j]

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

const int mSize = 100;
vector<int> G[mSize];
vector<vector<int>> bridge(mSize, vector<int>(mSize));
vector<int> visited(mSize), vk(mSize, -1), l(mSize, -1);
vector<pair<int, int>> edges;
int n, m, t;

void depthSearch(int v, int p = -1) {
    visited[v] = 1;
    vk[v] = l[v] = t++;
    for (auto x : G[v]) {
        if (x == p) continue;
        if (visited[x]) l[v] = min(l[v], vk[x]);
        else {
            depthSearch(x, v);
            l[v] = min(l[v], l[x]);
            if (l[x] > vk[v]) bridge[v][x] = 1;
        }
    }
}

void bridgeSearch() {
    t = 0;
    for (int i = 1; i <= n; ++i)
        if (!visited[i]) depthSearch(i);
}

int solve() {
    for (int i = 0; i < m; ++i) {
        int a = edges[i].first, b = edges[i].second;
        G[a].push_back(b); G[b].push_back(a);
    }
    bridgeSearch();
    int ans = 0;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            if (i != j && bridge[i][j]) ans++;
    return ans;
}

int main() {
    n = 5, m = 6;
    edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}};
    cout << solve();
    return 0;
}

อินพุต / เอาต์พุต

Input: 5, 6, {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}

Output: 1