并查集 洛谷(P3367)
在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将属于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复出现在信息学的国际国内赛题中，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受;即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间(1~3秒)内计算出试题需要的结果，只能用并查集来描述
输入输出格式
输入格式：
第一行包含两个整数N、M，表示共有N个元素和M个操作。
接下来M行，每行包含三个整数Zi、Xi、Yi
当Zi=1时，将Xi与Yi所在的集合合并
当Zi=2时，输出Xi与Yi是否在同一集合内，是的话输出Y；否则话输出N
输出格式：
如上，对于每一个Zi=2的操作，都有一行输出，每行包含一个大写字母，为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;//规定i的祖先为自己
for(i=1;i<=m;i++){
cin>>p1>>p2>>p3;
if(p1==1)
f[find(p2)]=find(p3); //令p2的祖先为p3的祖先
//合并操作就是把一个节点的祖先变为另一个节点的祖先
else
if(find(p2)==find(p3))
printf("Y\n");
else
printf("N\n");
}
return 0;
}
并查集的单次查询理想复杂度应该是O(logn)的，但是如果有一个这样的数据，并查集的复杂度就是O(n)了
为了避免这种情况，我们需对路径进行压缩。
即当我们经过找到祖先节点后，回溯的时候顺便将它的子孙节点都直接指向祖先，使以后的查找复杂度变回O(logn)甚至更低，让
