Solutions of Minimum spanning tree

Select solution language

MINHSANGNOAC Created at 0 likes

Bài này giải bằng thuật toán **[Kruskal](https://wiki.vnoi.info/algo/graph-theory/minimum-spanning-tree.md#1-thu%E1%BA%ADt-to%C3%A1n-kruskal)** kết hợp với DSU ``` #include <bits/stdc++.h> #define N 100020 using namespace std; struct graph { int u, v, w; }; int n, m, cnt = 0, e = 0; int parent[N]; graph edge[N]; void MakeSet() { for (int i = 1; i <= n; i++) parent[i] = i; } int Find(int u) { if (u == parent[u]) return u; int v = Find(parent[u]); parent[u] = v; return v; } void Union(int u, int v) { int a = Find(u); int b = Find(v); if (a == b) return; parent[a] = b; } int main() { cin >> n >> m; MakeSet(); for (int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; edge[i].u = u, edge[i].v = v, edge[i].w = w; } sort(edge + 1, edge + 1 + m, [](graph a, graph b){ return a.w < b.w; }); int i = 1; while (cnt < n - 1 && i <= m) { int u = edge[i].u, v = edge[i].v; if (Find(u) == Find(v)) { i++; continue; } Union(u, v); cnt++; e += edge[i].w; i++; } cout << e; } ```