Redundant Connection – หาขอบซ้ำในกราฟต้นไม้ C++

ปัญหา: Redundant Connection

มีกราฟที่เริ่มต้นเป็น Tree (N โหนด, ไม่มี cycle) เพิ่มขอบ 1 ขอบเข้าไป → กลายเป็นกราฟที่มี cycle 1 วง
หาขอบที่ลบออกได้เพื่อให้กลายเป็น Tree อีกครั้ง ถ้ามีหลายขอบ ให้คืน ขอบที่ปรากฎทีหลังสุด ในอินพุต

ตัวอย่าง

Edges: [[1,2], [2,3], [3,4], [1,4], [1,5]]

Output: [1,4] (ขอบที่ 4 สร้าง cycle 1-2-3-4-1)

แนวทางแก้ปัญหา: Union-Find (Disjoint Set Union)

หลักการ

• วนขอบตามลำดับ
• แต่ละขอบ (u,v) – ตรวจสอบว่า u และ v อยู่ใน component เดียวกันหรือไม่
  • ถ้าใช่ → ขอบนี้สร้าง cycle → เป็นคำตอบ (เก็บไว้ เพราะต้องการตัวทีหลังสุด)
  • ถ้าไม่ใช่ → Union(u,v) รวม component
• คืนขอบล่าสุดที่ทำให้เกิด cycle

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

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

class DSU {
    vector<int> parent, rank;
public:
    DSU(int n) : parent(n+1), rank(n+1, 0) {
        iota(parent.begin(), parent.end(), 0);
    }
    int find(int x) {
        return parent[x] == x ? x : parent[x] = find(parent[x]);
    }
    bool unite(int a, int b) {
        int pa = find(a), pb = find(b);
        if (pa == pb) return false; // cycle detected
        if (rank[pa] < rank[pb]) swap(pa, pb);
        parent[pb] = pa;
        if (rank[pa] == rank[pb]) rank[pa]++;
        return true;
    }
};

class Solution {
public:
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        DSU dsu(1000); // N <= 1000
        vector<int> ans;
        for (auto& e : edges) {
            if (!dsu.unite(e[0], e[1]))
                ans = e; // เก็บขอบที่ทำ cycle (ทับซ้อนตัวเก่า → ได้ตัวทีหลังสุด)
        }
        return ans;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> edges = {{1,2},{2,3},{3,4},{1,4},{1,5}};
    auto ans = ob.findRedundantConnection(edges);
    cout << ans[0] << ' ' << ans[1]; // 1 4
    return 0;
}

โค้ดต้นฉบับ (Array-based Union-Find)

const int N = 1000;
int parent[N+5], rnk[N+5];

int getParent(int n) {
    return parent[n] == -1 ? n : parent[n] = getParent(parent[n]);
}
bool unionn(int a, int b) {
    int pa = getParent(a), pb = getParent(b);
    if (pa == pb) return false;
    if (rnk[pa] > rnk[pb]) { rnk[pa] += rnk[pb]; parent[pb] = pa; }
    else { rnk[pb] += rnk[pa]; parent[pa] = pb; }
    return true;
}

ความซับซ้อน

• เวลา: O(N α(N)) ≈ O(N) – α = inverse Ackermann (near constant)
• พื้นที่: O(N)

ข้อสังเกต

• LeetCode 684 – Union-Find คลาสสิก
• Path Compression + Union by Rank = ใกล้ O(1) ต่อ operation
• โจทย์ขอ "last in input" → แค่ทับซ้อนคำตอบทุกครั้งที่เจอ cycle
• กรณี N ใหญ่ ควรใช้ vector แทน array ขนาดคงที่