| 1 | #include "../data-structures/union_find.cpp" |
| 2 | vector<pair<int, ii> > mst(int n, |
| 3 | vector<pair<int, ii> > edges) { |
| 4 | union_find uf(n); |
| 5 | sort(edges.begin(), edges.end()); |
| 6 | vector<pair<int, ii> > res; |
| 7 | rep(i,0,size(edges)) |
| 8 | if (uf.find(edges[i].second.first) != |
| 9 | uf.find(edges[i].second.second)) { |
| 10 | res.push_back(edges[i]); |
| 11 | uf.unite(edges[i].second.first, |
| 12 | edges[i].second.second); } |
| 13 | return res; } |
| 14 | // vim: cc=60 ts=2 sts=2 sw=2: |