Basic MST Questions

struct UnionFind {
    vector<int> parent, rank;
    int components;
 
    UnionFind(int n) : parent(n), rank(n, 0), components(n) {
        iota(parent.begin(), parent.end(), 0);
    }
 
    int find(int x) {
        if (parent[x] != x) parent[x] = find(parent[x]);
        return parent[x];
    }
 
    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);
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        components--;
        return true;
    }
 
    bool connected(int x, int y) { return find(x) == find(y); }
};

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
 
    def unite(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.components -= 1
        return True
 
    def connected(self, x, y):
        return self.find(x) == self.find(y)

class UnionFind {
    int[] parent, rank;
    int components;
 
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        components = n;
        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];
    }
 
    boolean unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false;
        if (rank[px] < rank[py]) { int t = px; px = py; py = t; }
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        components--;
        return true;
    }
 
    boolean connected(int x, int y) { return find(x) == find(y); }
}

int countComponents(int n, vector<vector<int>>& edges) {
    UnionFind uf(n);
    for (auto& e : edges) uf.unite(e[0], e[1]);
    return uf.components;
}

def count_components(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.unite(u, v)
    return uf.components

int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] e : edges) uf.unite(e[0], e[1]);
    return uf.components;
}

bool hasCycle(int n, vector<vector<int>>& edges) {
    UnionFind uf(n);
    for (auto& e : edges) {
        if (!uf.unite(e[0], e[1])) return true;  // already connected
    }
    return false;
}

def has_cycle(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        if not uf.unite(u, v):
            return True    # u and v already in same component
    return False

boolean hasCycle(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] e : edges)
        if (!uf.unite(e[0], e[1])) return true;
    return false;
}

def mst_cost(n, edges):
    # edges: list of [u, v, weight]
    edges.sort(key=lambda e: e[2])
    uf = UnionFind(n)
    total = added = 0
    for u, v, w in edges:
        if uf.unite(u, v):
            total += w
            added += 1
            if added == n - 1:
                return total
    return -1   # graph not fully connected

def would_create_cycle(n, tree_edges, new_u, new_v):
    uf = UnionFind(n)
    for u, v in tree_edges:
        uf.unite(u, v)
    return uf.find(new_u) == uf.find(new_v)