Could you tell wha
  • 板块P1536 村村通
  • 楼主fldfld
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/2 00:05
  • 上次更新2023/10/27 17:26:21
查看原帖
Could you tell wha
345765
fldfld楼主2022/8/2 00:05

我不到啊 没活啦

import java.io.IOException;
import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
    static StreamTokenizer st =new StreamTokenizer(in);
    public static int nextInt() throws IOException {
        st.nextToken();
        return (int)st.nval;
    }
    static int n;
    static int m;
    static int fa[];
//    static int size[];
    public static void main(String[] args) throws IOException {
        String line;
        while(true){
          
            String strs[] = in.readLine().split(" ");
            n  = Integer.parseInt(strs[0]);
            if(n == 0){
                break;
            }
            m =  Integer.parseInt(strs[1]);
            fa = new int[n+1];
            for(int i = 1;i<n+1;i++){
                fa[i] = i;
            }
            for (int i = 0; i < m; i++) {
                // int u = nextInt();
                // int v = nextInt();
                 String strs2[] = in.readLine().split(" ");
                 int u =Integer.parseInt(strs2[0]);
                 int v= Integer.parseInt(strs2[1]);
                join(u,v);
            }
        //   HashSet<Integer> set =new HashSet<>();
        //     for(int i = 1;i<n+1;i++){
        //         set.add(fa[i]);
        //     }
        int ans =0;
         for(int i = 1; i <= n; i++)
	    {
	    	if(find(i) == i)//自己的父亲等于自己本身
	    	{
	    		ans++;
			}
		}
            
            System.out.println(ans-1);
        }
    }
    static int find(int x){
        int res = x;
        while(res != fa[res]){
            res = fa[res];
        }
        return res;
    }
    static void join(int x,int y){
        if(find(x) != find(y)){
           fa[x] = y;
        }
    }
}

2022/8/2 00:05
加载中...