全部笔记提示
接下来整理的笔记，有一个很重要的是初始化，如果不初始化，运行以后题目可能不会输出。
并查集笔记
算法解释
建边，由于挨个挨个查找比较麻烦所以要进行【路径压缩】，让每一个节点直接指向根节点。（之所以可以这么做，是因为题目只询问两点是否在同一集合）
代码解释
并查集类型的题主要由4个（包括初始化）函数构成：
- init函数：初始化（最重要的一步，不添加会不输出）。
- find函数：查找这个节点的根节点。
- unite函数：建边，由于可能将两个图（更准确的来说是树）的根节点连到一起这时无论是哪一个节点（下称X）指向另一个节点（下称Y），根据【路径压缩】，指向Y的X其下的子节点会分别指向Y，所以我们要让节点最少的树的根节点指向节点更多的树的根节点。这样时间才会更快。（but，这个连接条件会因题目而异）。
*same函数（因题而异）：判断两点是否在一个集合内。
模板代码
P3367 【模板】并查集
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,m;
int fa[N],sz[N];
void init()
{for(int i=1;i<=n;i++){fa[i]=i;sz[i]=1;}
}
int find(int x)
{if(fa[x]!=x){fa[x]=find(fa[x]);}return fa[x];
}
void unite(int x,int y)
{int fx=find(x);int fy=find(y);if(fx==fy) return ;if(sz[fx]<sz[fy]){swap(fx,fy);}fa[fy]=fx;sz[fx]+=sz[fy];
}
bool same(int x,int y)
{return find(x)==find(y);
}
int main()
{cin>>n>>m;init();for(int i=1;i<=m;i++){int x,y,z;cin>>z>>x>>y;if(z==1){unite(x,y);}else{if(same(x,y)){cout<<"Y"<<"\n";}else{cout<<"N"<<"\n";}} }return 0;
}