并查集 洛谷(P3367)
? ?????在一些有N個(gè)元素的集合應(yīng)用問(wèn)題中赫编，我們通常是在開(kāi)始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并腋逆，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。這一類問(wèn)題近幾年來(lái)反復(fù)出現(xiàn)在信息學(xué)的國(guó)際國(guó)內(nèi)賽題中，其特點(diǎn)是看似并不復(fù)雜蒋畜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來(lái)描述的話撞叽，往往在空間上過(guò)大姻成，計(jì)算機(jī)無(wú)法承受;即使在空間上勉強(qiáng)通過(guò)，運(yùn)行的時(shí)間復(fù)雜度也極高愿棋，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間(1~3秒)內(nèi)計(jì)算出試題需要的結(jié)果科展，只能用并查集來(lái)描述
輸入輸出格式
輸入格式：
第一行包含兩個(gè)整數(shù)N、M糠雨，表示共有N個(gè)元素和M個(gè)操作辛润。
接下來(lái)M行，每行包含三個(gè)整數(shù)Zi、Xi砂竖、Yi
當(dāng)Zi=1時(shí)真椿，將Xi與Yi所在的集合合并
當(dāng)Zi=2時(shí)，輸出Xi與Yi是否在同一集合內(nèi)乎澄，是的話輸出Y突硝；否則話輸出N
輸出格式：
如上，對(duì)于每一個(gè)Zi=2的操作置济，都有一行輸出解恰，每行包含一個(gè)大寫(xiě)字母，為Y或者N
輸入樣例#1：
4 7
2 1 2
1 1 2
2 1 2
1 3 4
2 1 4
1 2 3
2 1 4
輸出樣例#1：
N
Y
N
Y
#include<bits/stdc++.h>
using namespace std;
int i,j,k,n,m,s,ans,f[10010],p1,p2,p3;
//f[i]表示i的集合名
int find(int k){
//路徑壓縮
if(f[k]==k)return k;
return f[k]=find(f[k]);
}
int main()
{
cin>>n>>m;
for(i=1;i<=n;i++)
f[i]=i;//規(guī)定i的祖先為自己
for(i=1;i<=m;i++){
cin>>p1>>p2>>p3;
if(p1==1)
f[find(p2)]=find(p3); //令p2的祖先為p3的祖先
//合并操作就是把一個(gè)節(jié)點(diǎn)的祖先變?yōu)榱硪粋€(gè)節(jié)點(diǎn)的祖先
else
if(find(p2)==find(p3))
printf("Y\n");
else
printf("N\n");
}
return 0;
}
并查集的單次查詢理想復(fù)雜度應(yīng)該是O(logn)的浙于，但是如果有一個(gè)這樣的數(shù)據(jù)护盈，并查集的復(fù)雜度就是O(n)了
為了避免這種情況，我們需對(duì)路徑進(jìn)行壓縮羞酗。
即當(dāng)我們經(jīng)過(guò)找到祖先節(jié)點(diǎn)后腐宋，回溯的時(shí)候順便將它的子孫節(jié)點(diǎn)都直接指向祖先，使以后的查找復(fù)雜度變回O(logn)甚至更低檀轨，讓
