E-MST1(EmsT1106155085469)

来源：恒创科技编辑：恒创科技编辑部

2024-01-08 11:38:59

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 2e5 + 10;

int p[N];
bool st[N];
int n, m, q;
struct Node {
    int w, u, v, id;
    bool operator< (const Node&q) {
        return w < q.w;
    }
}queries[N], edges[N];
int find(int x) {
    if (x != p[x]) p[x] = find(p[x]);
    return p[x];
}
int merge (int a, int b) {
    int pa = find(a), pb = find(b);
    if (pa == pb) return 0;
    p[pa] = pb;
    return 1;
}
int main() { 
    cin>> n >> m >> q;

    for (int i = 0; i < m;i ++) {
        int u, v, w;
        cin >> u >> v >> w;
        u --, v --;
        edges[i].u = u, edges[i].v = v, edges[i].w = w;
    }
    for (int i =1; i<= n;  i++) p[i] = i;
    sort(edges, edges + m);
    for (int i = 0; i < q; i ++) {
        int u, v, w;
        cin >> u >> v>> w;
        u --, v --;
        queries[i].u = u, queries[i].v = v, queries[i].w = w;
        queries[i].id = i;
    }
    sort(queries, queries+ q);
    for (int i = 0, j = 0; i< q; i++) {
        while (j < m && edges[j].w < queries[i].w) {
            merge(edges[j].u, edges[j].v);
            j ++;
        }
        int a = find(queries[i].u), b = find(queries[i].v);
        if (a != b) {
            st[queries[i].id] = 1;
        }
    }
    for (int i = 0; i <q; i ++)
        if (st[i]) puts("Yes");
        else puts("No");
    return 0;
}