Luogu P3367 【模板】並查集

題目描述

如題，現在有一個並查集，你需要完成合併和查詢操作。

輸入輸出格式

輸入格式：

第一行包含兩個整數N、M，表示共有N個元素和M個操作。

接下來M行，每行包含三個整數Zi、Xi、Yi

當Zi=1時，將Xi與Yi所在的集合合併

當Zi=2時，輸出Xi與Yi是否在同一集合內，是的話輸出Y；否則話輸出N

輸出格式：

如上，對於每一個Zi=2的操作，都有一行輸出，每行包含一個大寫字母，為Y或者N

輸入輸出樣例

4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4

N
Y
N
Y

說明

時空限制：1000ms,128M

數據規模：

對於30%的數據，N<=10，M<=20；

對於70%的數據，N<=100，M<=1000；

對於100%的數據，N<=10000，M<=200000。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int read()
 4 {
 5 int ret=0,ok=1;
 6 char ch=getchar();
 7 while(ch<'0'||ch>'9')
 8 {
 9 if(ch=='-')ok=-1;
10 ch=getchar();
11 }
12 for(;ch>='0'&&ch<='9';ch=getchar())
13  ret=ret*10+ch-'0';
14 return ret*ok;
15 }
16 int n,m,z,x,y; 
17 int father[10002];
18 inline int find(int i)
19 {
20     if(i==father[i])
21     return i;
22     while(i!=father[i])
23     i=father[i];
24     return father[i];
25 }
26 inline void unionn(int i,int j)
27 {
28     int r1=find(i),r2=find(j);
29     if(r1==r2)
30     return ;
31      father[r2]=r1;
32     father[j]=r1;
33     return ;
34 }
35 int main()
36 {
37 //freopen(".in","r",stdin);
38 //freopen(".out","w",stdout);
39 n=read(),m=read();
40 for(int i=1;i<=n;i++)
41 father[i]=i;
42 for(int i=1;i<=m;i++)
43 {
44     z=read(),x=read(),y=read();
45     switch(z){
46         case 1:{
47             unionn(x,y);
48             break;
49         }
50         case 2:{
51             if(find(x)==find(y))
52             cout<<"Y"<<endl;
53             else
54             cout<<"N"<<endl;
55             break;
56         }        
57     }    
58 }
59     return 0;
60 }

圖論中的一個較經常考察的點：並查集。就是需要一個unionn(x,y)的合併問題和一個find(x)找父親問題。

並查集首先就是先把自己指向自己做自己的父親，等到後面找別人來做自己的父親，一層一層上去，但是此題要註意的是路徑壓縮問題，路徑沒壓縮的話就會3個點超時。

我們來平民化一下並查集的概念（很早以前從一個博客上看到的，我用自己的語言組織了一下）：

【平民化概念】：

在金庸小說的世界里，門派很多，經常會發生一些爭鬥，而且一般來說一個大的勢力首先都需要自己出頭來做老大，所以這個時候你自己的這個門派的老大就是你自己，即father[you]=you

後來，在你冒險的過程中你開始結識了一群很牛逼的好友，你覺得應該把他們拉到自己的門下，那麼這個時候你就勸說他們把他們的門派老大指向你，意思就是說你是他們的老大，即father[別人]=you

但是你只是認識了這些比你低一級別的屬下，你屬下的屬下和他屬下的屬下都互相不認識啊，這個時候就很容易起爭端還不知道是自己人，互相打來打去（怎麼這麼傻），萬一有一天在小樹林里碰面，A、B二人都不知道對方是敵是友，如果要一級一級上報上去，顯然是可以做到的，但是其中所耗費的時間必然是我們所比較不願意接受的，所以我們希望我們屬下的屬下，他的老闆就是我，意思就是說他可以直接認識我，並且接觸到我，這樣的話兩人看到，就可能說：“在下是饕餮的屬下”，“誒，我是Hammer他屬下XX的屬下，我們兩個是朋友”然後兩個人就手拉手一起走上人生巔峰了。。。。。這裡的代碼轉換一下即：判斷一下是敵是友（int x=find(A),y=find(B)解釋：x是A的頂頭上司，y是B的頂頭上司)如果不認識，那麼認識一個朋友就是一個保障嘛，那麼這個時候：father[x]=y，但是你會發現如果這樣，一層一層地上報豈不是很麻煩，那麼你就可以直接father[A]=y就可以啦，這就是一個非常簡單的路徑壓縮啦