SW练习_ADV_农林水路_unionFind-CSDN博客

本文链接：https://blog.csdn.net/mush_me/article/details/107676536

本文详细介绍了如何运用并查集（unionFind）算法解决SW练习中涉及的农林水路连接问题。通过实例解析，探讨了如何通过并查集有效地维护联通组件，并给出具体步骤和实现代码，帮助读者理解和应用该算法。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

package info.frady.adv;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class NonglinShuilu {
    public static int[] set;
    public static void main(String[] args) throws Exception{
        System.setIn(new FileInputStream("C:\\Users\\86153\\Desktop\\SW\\adv\\20\\eval_input.txt"));
        //System.setIn(new FileInputStream("C:\\Users\\86153\\Desktop\\SW\\adv\\20\\sample_input.txt"));

        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(reader.readLine());
        int T=Integer.parseInt(st.nextToken());
        for (int i = 0; i <T ; i++) {
            st=new StringTokenizer(reader.readLine());
            int N=Integer.parseInt(st.nextToken());//农田的个数
            int M=Integer.parseInt(st.nextToken());//水路，其实就是边的个数
            set=new int[N+1];
            init();//初始化数组
            for (int j = 0; j <M ; j++) {
                st=new StringTokenizer(reader.readLine());
                int a=Integer.parseInt(st.nextToken());
                int b=Integer.parseInt(st.nextToken());
                if(!connected(a,b)){
                    union(a,b);
                }
                //System.out.println(Arrays.toString(set));
            }
            int count=0;
            for (int j = 0; j <set.length ; j++) {
                if(find(j)!=0){
                    count++;
                }

            }
            System.out.printf("#%d %d\n",(i+1),count);
        }

        reader.close();
    }

    public static void init(){
        for (int i = 0; i <set.length ; i++) {
            set[i]=i;
        }
    }

    public static void union(int a,int b){
        int A=find(a);
        int B=find(b);
        if(A!=B){
            if(A<B){
                set[B]=A;//把大的点挂到小的上面
            }else{
                set[A]=B;
            }

        }
    }
    public static boolean connected(int a,int b){
        int A=find(a);
        int B=find(b);
        return A==B;
    }

    public static int find(int a){
        if(set[a]==a){
            return set[a];
        }
        return set[a]=find(set[a]);
    }
}