一共有n個數，編號是1~n，最開始每個數各自在一個集合中，
現在要進行m個操作，操作共有兩種：
- “M a b”，將編號為a和b的兩個數所在的集合合并，如果兩個數已經在同一個集合中，則忽略這個操作；
- “Q a b”，詢問編號為a和b的兩個數是否在同一個集合中；
輸入格式
第一行輸入整數n和m，
接下來m行，每行包含一個操作指令，指令為“M a b”或“Q a b”中的一種，
輸出格式
對于每個詢問指令”Q a b”，都要輸出一個結果，如果a和b在同一集合內，則輸出“Yes”，否則輸出“No”，
每個結果占一行，
資料范圍
1≤n,m≤1051≤n,m≤105
輸入樣例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
輸出樣例：
Yes
No
Yes
import java.util.Scanner; public class Main{ static int n,m; static final int N=100005; static int p[]=new int[N]; static int find(int x){ //回傳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; while(m-->0){ String s=scan.next(); int a=scan.nextInt(); int b=scan.nextInt(); if(s.equals("M")){//如果兩個數在一個集合里，可以直接忽略 p[find(a)]=find(b);//集合合并 } else{ if(find(a)==find(b)) System.out.println("Yes"); else System.out.println("No"); } } } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/102331.html
標籤：其他
上一篇：并查集模板