1138. 城市公交网建设问题

Kruskal 算法

#include <bits/stdc++.h>

using namespace std;
const int maxn = 105, maxm = 10005;
int n, m, fa[maxn];

vector<pair<int,int> > ans;
struct Edge{
    int x, y, val;
    bool operator < (const Edge &tmp) const{
        return val < tmp.val;
    }
}e[maxm];

int getfa(int x){
    if(x == fa[x]) return x;
    return fa[x] = getfa(fa[x]);
}

void kruskal(){
    sort(e, e + m);
    for(int i = 0; i < m; ++ i){
        int fx = getfa(e[i].x), fy = getfa(e[i].y);
        if(fx != fy){
            ans.push_back({e[i].x, e[i].y});
            fa[fx] = fy;
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; ++ i) fa[i] = i;
    for(int i = 0, x, y, z; i < m; ++ i){
        cin >> x >> y >> z;
        e[i].x = x, e[i].y = y, e[i].val = z;
    }
    kruskal();
    for(auto it: ans)
        cout << it.first << " " << it.second << endl;
    return 0;
}