ICPC Competitive Programming
← กลับหน้าหลัก

Disjoint Set Union (DSU)

โครงสร้างข้อมูล Union-Find สำหรับจัดการกลุ่ม

Disjoint Set Union (DSU)

Disjoint Set Union (DSU) หรือ Union-Find เป็นโครงสร้างข้อมูลที่ใช้จัดการ กลุ่มที่ไม่ซ้อนทับกัน (disjoint sets)

Operations

  1. MakeSet(x): สร้าง set ใหม่ที่มี x เพียงตัวเดียว
  2. Find(x): หา representative (root) ของ set ที่ x อยู่
  3. Union(x, y): รวม set ที่มี x และ y เข้าด้วยกัน

Basic Implementation

class DSU {
private:
    vector<int> parent, rank_;
    
public:
    DSU(int n) {
        parent.resize(n);
        rank_.resize(n, 0);
        
        // Initially, each element is its own parent
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // Already in same set
        
        // Union by rank
        if (rank_[px] < rank_[py]) swap(px, py);
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
};

Optimizations

1. Path Compression

ทำให้ทุก node ชี้ไปที่ root โดยตรง

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]); // Compress path
    }
    return parent[x];
}

2. Union by Rank/Size

รวม tree ที่เล็กกว่าเข้ากับ tree ที่ใหญ่กว่า

// Union by Rank
void unite(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    
    if (rank_[px] < rank_[py]) swap(px, py);
    parent[py] = px;
    if (rank_[px] == rank_[py]) rank_[px]++;
}

// Union by Size
void uniteBySize(int x, int y) {
    int px = find(x), py = find(y);
    if (px == py) return;
    
    if (size_[px] < size_[py]) swap(px, py);
    parent[py] = px;
    size_[px] += size_[py];
}

DSU with Additional Info

Track Set Size

class DSUWithSize {
private:
    vector<int> parent, size_;
    
public:
    DSUWithSize(int n) {
        parent.resize(n);
        size_.resize(n, 1);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        
        if (size_[px] < size_[py]) swap(px, py);
        parent[py] = px;
        size_[px] += size_[py];
    }
    
    int getSize(int x) {
        return size_[find(x)];
    }
    
    int countSets() {
        int count = 0;
        for (int i = 0; i < parent.size(); i++) {
            if (parent[i] == i) count++;
        }
        return count;
    }
};

Track Component Sum

class DSUWithSum {
private:
    vector<int> parent;
    vector<long long> sum;
    
public:
    DSUWithSum(vector<int>& arr) {
        int n = arr.size();
        parent.resize(n);
        sum.resize(n);
        
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            sum[i] = arr[i];
        }
    }
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return;
        
        parent[py] = px;
        sum[px] += sum[py];
    }
    
    long long getSum(int x) {
        return sum[find(x)];
    }
};

Applications

1. Connected Components

int countConnectedComponents(int n, vector<pair<int, int>>& edges) {
    DSU dsu(n);
    
    for (auto [u, v] : edges) {
        dsu.unite(u, v);
    }
    
    int count = 0;
    for (int i = 0; i < n; i++) {
        if (dsu.find(i) == i) count++;
    }
    
    return count;
}

2. Cycle Detection in Undirected Graph

bool hasCycle(int n, vector<pair<int, int>>& edges) {
    DSU dsu(n);
    
    for (auto [u, v] : edges) {
        if (dsu.find(u) == dsu.find(v)) {
            return true; // Cycle found
        }
        dsu.unite(u, v);
    }
    
    return false;
}

3. Kruskal’s MST

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

long long kruskalMST(int n, vector<Edge>& edges) {
    sort(edges.begin(), edges.end());
    DSU dsu(n);
    
    long long mstWeight = 0;
    int edgeCount = 0;
    
    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mstWeight += e.w;
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }
    
    return mstWeight;
}

4. Friend Groups / Social Network

int findCircleNum(vector<vector<int>>& isConnected) {
    int n = isConnected.size();
    DSU dsu(n);
    
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (isConnected[i][j]) {
                dsu.unite(i, j);
            }
        }
    }
    
    int groups = 0;
    for (int i = 0; i < n; i++) {
        if (dsu.find(i) == i) groups++;
    }
    
    return groups;
}

5. Redundant Connection (หา edge ที่ทำให้เกิด cycle)

pair<int, int> findRedundant(vector<pair<int, int>>& edges) {
    int n = edges.size();
    DSU dsu(n + 1);
    
    for (auto [u, v] : edges) {
        if (!dsu.unite(u, v)) {
            return {u, v}; // This edge creates a cycle
        }
    }
    
    return {-1, -1};
}

DSU Variations

Weighted DSU (DSU with Distance)

เก็บระยะห่างระหว่าง node กับ root

class WeightedDSU {
private:
    vector<int> parent;
    vector<long long> dist; // distance to parent
    
public:
    WeightedDSU(int n) {
        parent.resize(n);
        dist.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    pair<int, long long> find(int x) {
        if (parent[x] == x) return {x, 0};
        
        auto [root, d] = find(parent[x]);
        parent[x] = root;
        dist[x] += d;
        
        return {root, dist[x]};
    }
    
    void unite(int x, int y, long long w) {
        // x - y = w (set relation)
        auto [px, dx] = find(x);
        auto [py, dy] = find(y);
        
        if (px == py) return;
        
        parent[py] = px;
        dist[py] = dx - dy + w;
    }
    
    long long getDist(int x, int y) {
        auto [px, dx] = find(x);
        auto [py, dy] = find(y);
        
        if (px != py) return LLONG_MAX; // Not in same set
        return dy - dx;
    }
};

Rollback DSU (Undo operations)

ใช้เมื่อต้องการ undo union operations

class RollbackDSU {
private:
    vector<int> parent, rank_;
    vector<pair<int*, int>> history;
    
public:
    RollbackDSU(int n) {
        parent.resize(n);
        rank_.resize(n, 0);
        for (int i = 0; i < n; i++) parent[i] = i;
    }
    
    int find(int x) {
        while (parent[x] != x) x = parent[x];
        return x;
        // Note: No path compression for rollback support
    }
    
    bool unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        
        if (rank_[px] < rank_[py]) swap(px, py);
        
        // Save history
        history.push_back({&parent[py], parent[py]});
        history.push_back({&rank_[px], rank_[px]});
        
        parent[py] = px;
        if (rank_[px] == rank_[py]) rank_[px]++;
        
        return true;
    }
    
    int checkpoint() {
        return history.size();
    }
    
    void rollback(int cp) {
        while (history.size() > cp) {
            auto [ptr, val] = history.back();
            *ptr = val;
            history.pop_back();
        }
    }
};

Complexity

OperationTime (with optimizations)
MakeSetO(1)O(1)
FindO(α(n))O(\alpha(n)) ≈ O(1)O(1)
UnionO(α(n))O(\alpha(n)) ≈ O(1)O(1)

α(n)\alpha(n) คือ inverse Ackermann function ซึ่งโตช้ามากๆ (สำหรับ nn ที่เป็นไปได้ในทางปฏิบัติ α(n)≤4\alpha(n) \leq 4)

สรุป

Use CaseDSU Variant
Basic connectivityStandard DSU
Track set size/sumDSU with additional data
MST (Kruskal)Standard DSU
Need undoRollback DSU
Relations with weightsWeighted DSU

💡 Tip: DSU เป็น data structure ที่ใช้บ่อยมากในการแข่งขัน ควรจำ template ให้ขึ้นใจ