蓝桥杯历届试题-国王的烦恼 （C++代码）

解题思路:

注意事项:

参考代码:

#include <iostream>
#include <algorithm>
using namespace std;
int *parent;
int *sz;

typedef struct{
    int a,b,t;
}bridge;
bridge *arr;

int cmp(const void* a,const void* b){
    bridge *x = (bridge *)a;
    bridge *y = (bridge *)b;
    return x->t < y->t;
}

void initializationUnionFind(int n){
    for(int i=1;i<=n;i++){
        parent[i] = i;
        sz[i] = 1;
    }
}

int find(int p){
    if(parent[p] != p)
        return find(parent[parent[p]]);
    return parent[p];
}
bool isConnected(int p,int q){
    return find(p) == find(q);   
}

bool unionElement(int p,int q){
    int pRoot = find(p);
    int qRoot = find(q);
    
    if(pRoot == qRoot)
        return false;
    
    if(sz[pRoot] > sz[qRoot]){
        parent[qRoot] = pRoot;
    }else if(sz[pRoot] < sz[qRoot]){
        parent[pRoot] = qRoot;
    }else{
        parent[qRoot] = pRoot;
        sz[pRoot]++;
    }
    return true;
}

int king(){
    int n,m;
    cin >> n >> m;
    parent = new int [n+1];
    sz = new int [n+1];
    arr = new bridge [m+1];
    initializationUnionFind(n);
    for(int i=1;i<=m;i++){
        cin >> arr[i].a >> arr[i].b >> arr[i].t;
    }
    qsort(arr+1,m,sizeof(arr[1]),cmp);
    
    int lastDay = -1;
    int days = 0;
    for(int i=1;i<=m;i++){
        if(unionElement(arr[i].a,arr[i].b) && lastDay != arr[i].t ){
            days++;
            lastDay = arr[i].t;
        }
            
    }
    cout << days;
    delete [] arr;
    delete [] parent;
    delete [] sz;
}

int main(){
    king();
    return 0;
}