Thuật toán Kruskal

Kiến thức cần biết

• Disjoint Set Union

Khái niệm

Ví dụ

Cho đồ thị vô hướng

$G$ gồm

$n$ đỉnh và

$m$ cạnh nối giữa 2 đỉnh

$u,v$ với trọng số là

$w$. Tìm c

Cài đặt

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct DSU {
    vector<int> p, lvl;
    void init(int n) {
        p.resize(n+1);
        iota(begin(p), end(p), 0);
        lvl.assign(n, 0);
    }
    int find(int u) {return parent[u] == u ? u : (parent[u] = find(parent[u])); }
    bool unite(int u, int v) {
        
    }
    bool connected(int x, int y) { return find(x) == find(y); }
} dsu;

int main() {
    
}

Đánh giá độ phức tạp

Bài tập vận dụng

1. NKCITY
   Code mẫu

2. 1927 - F
   Code mẫu