closefrom

两题都是用并查集
最小生成树用的是kruskal算法

//并查集AC Code：
#include <cstdio>
using namespace std;
int n,m;
int zi,xi,yi;
int fd[10005];
int findfd(int x){
    while(x!=fd[x])x=fd[x]=fd[fd[x]];
    return x;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)fd[i]=i;
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&zi,&xi,&yi);
        int fx=findfd(xi);int fy=findfd(yi);
        if(zi==1)fd[fy]=fx;
        else if(zi==2){
            if(fx==fy)printf("Y\n");
            else printf("N\n");
        }
    }
    return 0;
}

//最小生成树 AC Code：
#include <cstdio>
#include <algorithm>
using namespace std;
int n,m,ans=0,cnt=0;
struct node{
    int x,y,z;
}nm[200005];
int fd[5005];
int findfather(int ft){
    while(ft!=fd[ft])ft=fd[ft]=fd[fd[ft]];
    return ft;
}
bool cp(node a,node k){return a.z<k.z;}
void kruskal(){
    for(int i=1;i<=m;i++){
        int fx=findfather(nm[i].x);int fy=findfather(nm[i].y);
        if(fx==fy)continue;
        ans+=nm[i].z;
        fd[fy]=fx;
        if(++cnt==n-1)break;
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&nm[i].x,&nm[i].y,&nm[i].z);
    for(int i=1;i<=n;i++)fd[i]=i;
    sort(nm+1,nm+m+1,cp);
    kruskal();
    printf("%d",ans);
    return 0;
}