并查集10分(真看不出哪里错了)
查看原帖
并查集10分(真看不出哪里错了)
394729
Weight_of_the_Soul楼主2021/6/1 18:55
#include <cstdio>
#include <algorithm>

using namespace std;

int n, m;
int dad[100005];

struct Node {
    int x, y, t;
}a[100005];

int anc(int x) {
    if(dad[x]) {
        return dad[x] = anc(dad[x]);
    }
    return x;
}

bool ask(int x, int y) {
    return anc(x) == anc(y);
}

void uni(int x, int y) {
    x = anc(x);
    y = anc(y);

    if(x != y) {
        dad[x] = y;
    }
}

void inp() {
    scanf("%d%d", &n, &m);

    for(register int i = 1; i <= m; i++) {
        scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].t);
    }
}

bool cmp(Node x, Node y) {
    return x.t < y.t;
}

void work() {
    for(register int i = 1; i <= m; i++) {
        uni(a[i].x, a[i].y);
        n--;
        if(n == 1) {
            printf("%d", a[i].t);
            return ;
        }
    }

    printf("-1");
}

int main() {
    inp();
    sort(a+1, a+1+m, cmp);
    work();
    return 0;
}
2021/6/1 18:55
加载中...