给定一个包含 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≤n,m≤1051≤n,m≤105
输入样例:
- 5 5
- C 1 2
- Q1 1 2
- Q2 1
- C 2 5
- Q2 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)]);
- }
- }
- }
- }
837. 连通块中点的数量(并查集)
来源: http://www.bubuko.com/infodetail-3395211.html