再来看看hdu并查集题目

首先是 hdu 3635

这里主要难点就是找到每个球的被搬运了多少次，可以使用数组来存储每个球的搬运次数，在路径压缩和合并的时候记得更新
当前节点的搬运次数

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e4 + 100 ;
int p[N] ;   //并查集
int tr[N] ;   //搬运次数
int st[N] ;   //状态，没用
int g[N] ;    //记录个数

int find(int x){
    if(x == p[x]) return p[x] ;
    int t = p[x] ;   //t是x的父节点
    p[x] = find(p[x]) ;
    tr[x] += tr[t] ;   //x的搬运次数等于x+上父节点搬运次数
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
        tr[fa] ++ ;     //fa搬运次数++
    }
}

int main()
{
    int t ;
    scanf("%d",&t) ;
    int ant = 1 ;
    while(t--){
        int n,m;
        scanf("%d %d",&n,&m) ;
        memset(tr,0,sizeof tr) ;
        memset(st,0,sizeof st) ;
        for(int i = 0 ; i <= n ; i++){
            p[i] = i ;
            g[i] = 1 ;
        }

        printf("Case %d:\n",ant ) ;
        ant ++;
        for(int i = 0 ; i < m  ;i ++){
            char opt ;
            scanf(" %c",&opt) ;
            if(opt == 'T'){
                int a,b ;
                scanf("%d %d",&a,&b) ;
                if(find(a) == find(b)){
                    continue;
                }
                g[find(b)] += g[find(a)] ;
                g[find(a)] = 0 ;
//                for(int i = 1 ; i<= n ; i++){
//                    if(find(i) == find(a) && !st[N]){
//                        tr[i]++ ;
//                    }
//                }
                marge(a,b) ;   //记得写对顺序，是谁搬运到谁哪里
            }
            else{
                int a;
                scanf("%d",&a) ;
                int cnt = 0 ;
//                for(int i = 1 ; i<= n ; i++){
//                    if(find(i) == find(a) && !st[N]){
//                        cnt++ ;
//                    }
//                }
                cnt = g[find(a)] ; 
                //st[a] = 1 ;
                printf("%d %d %d\n",find(a),cnt,tr[a]) ;
            }
        }

    }
    return 0;
}

hdu 1856
hdu 1856
这道题主要找到一个最大集合数量，使用并查集就可以了
将数量合并在合并marge中进行，对根节点数量进行合并

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5 + 100 ;
int p[N] ;
int g[N] ;

int find(int x){
    if(x != p[x]) p[x] = find(p[x]) ;
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        g[fb] += g[fa] ;
        g[fa] = 0 ;
        p[fa] = fb ;
    }
}

int main()
{
    int n ;
    while(~scanf("%d",&n)){

        for(int i = 0 ; i < N ; i++ ){
            p[i] = i ;
            g[i] = 1 ;
        }

        for(int i = 0 ; i < n ;i ++){
            int a,b ;
            scanf("%d %d",&a,&b) ;
            marge(a,b) ;
        }

        int maxd = 0 ;
        for(int i = 0 ; i < N ; i++){
            maxd = max(maxd,g[i]) ;
        }
        printf("%d\n",maxd) ;
    }
    return 0;
}

hdu 1272 小希的迷宫
1272 小希的迷宫

这道题是寻找有没有环，，可以使用并查集，如果找到两个节点的根是同一个，证明相连，现在又要相连，就会有环，
，，最后还要判断是否是一个集合

一定注意输出大小写

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int N = 1e5 + 100 ;
int p[N] ;
bool st[N] ;

int find(int x){
    if(x != p[x]) p[x] = find(p[x]) ;
    return p[x] ;
}

void marge(int a,int b){
    int fa = find(a) ;
    int fb = find(b) ;
    if(fa != fb){
        p[fa] = fb ;
    }
}
int main()
{
    int a,b ;
    while(scanf("%d %d",&a,&b),~a){
        if(a == 0 && b == 0){
            puts("Yes") ;     //这种情况下没有节点，会输出yes
            continue ;
        }
        bool flag = 0 ;
        for(int i = 0 ; i < N ; i++){
            p[i] = i ;
        }
        memset(st,0,sizeof st) ;
        while(a){
            if(find(a) == find(b) ){
                flag = 1 ;
            }
            marge(a,b) ;
            st[a] = 1 ,st[b] = 1;    //记录是否出现过
            scanf("%d %d",&a,&b) ;
        }
        if(flag){
            puts("No") ;
        }
        else{
            int cnt = 0 ;
            for(int i = 1 ; i <= N ; i++){
                if(st[i] && p[i] == i){
                    cnt ++ ;
                }
            }
            if(cnt == 1){
                puts("Yes") ;
            }
            else {
                puts("No") ;
            }
        }
    }
    return 0;
}