837. 連通塊中點的數量（并查集）-有解無憂

給定一個包含n個點（編號為1~n）的無向圖，初始時圖中沒有邊，

現在要進行m個操作，操作共有三種：

“C a b”，在點a和點b之間連一條邊，a和b可能相等；
“Q1 a b”，詢問點a和點b是否在同一個連通塊中，a和b可能相等；
“Q2 a”，詢問點a所在連通塊中點的數量；

輸入格式

第一行輸入整數n和m，

接下來m行，每行包含一個操作指令，指令為“C a b”，“Q1 a b”或“Q2 a”中的一種，

輸出格式

對于每個詢問指令”Q1 a b”，如果a和b在同一個連通塊中，則輸出“Yes”，否則輸出“No”，

對于每個詢問指令“Q2 a”，輸出一個整數表示點a所在連通塊中點的數量

每個結果占一行，

資料范圍

$1 \leq n, m \leq 10^{5}$

輸入樣例：

輸出樣例：

Yes
2
3

代碼：

import java.util.Scanner;

public class Main{
        static int n,m;
        static final int N=100005;
        static int p[]=new int[N];
        static int size[]=new int[N];//存盤的是一個集合元素的數量，只有根節點有效
        static int find(int x){
                if(p[x]!=x) p[x]=find(p[x]);
                return p[x];
        }
        public static void main(String[] args) {
                Scanner scan=new Scanner(System.in);
                n=scan.nextInt();
                m=scan.nextInt();
                for(int i=1;i<=n;i++){
                        p[i]=i;
                        size[i]=1;
                }
                while(m-->0){
                        String s=scan.next();
                        if(s.equals("C")){
                                int a=scan.nextInt();
                                int b=scan.nextInt();
                                if(find(a)==find(b)) continue;
                                size[find(b)]+=size[find(a)];//先加上再合并；否則就重復加了
                                p[find(a)]=find(b);
                        }
                        else if(s.equals("Q1")){
                                int a=scan.nextInt();
                                int b=scan.nextInt();
                                if(find(a)==find(b)) System.out.println("Yes");
                                else System.out.println("No");
                        }
                        else{
                                int a=scan.nextInt();
                                System.out.println(size[find(a)]);
                        }
                }
        }
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/100428.html

標籤：其他

上一篇：一文解讀ZooKeeper (轉)

下一篇：PAT乙級1021