AcWing 836. 合并集合(JAVA)
原题链接
简单
作者:
鼠鼠我
,
2021-01-31 22:56:37
,
所有人可见
,
阅读 293
package 第二章数据结构;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class 合并集合并查集 {
static int N = 100010;
static int[] p = new int[N];//p[i]代表i的祖宗结点
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String s[] = br.readLine().split("\\s+");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
for(int i=1;i<=n;i++) p[i] = i;
while(m-- >0)
{
String ss[] = br.readLine().split("\\s+");
int a = Integer.parseInt(ss[1]);
int b = Integer.parseInt(ss[2]);
if("M".equals(ss[0]))//合并集合
{
p[find(a)] = find(b);
}
else {//询问编号为a和b的两个数是否在同一个集合中;
if(find(a)==find(b))
bw.write("Yes"+"\n");
else bw.write("No"+"\n");
}
}
bw.flush();
br.close();
bw.close();
}
static int find(int x)//寻找x的祖宗结点
{
if(p[x]!=x) p[x] = find(p[x]);//每个集合中只有祖宗节点的p[x]值等于他自己,即:
return p[x];//返回祖宗结点
}
}