# Part 1
## 并查集的用处&时间复杂度
用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
时间复杂度:不压缩$O(nlog_n)$压缩$O(n)$
# Part 2
## 基础并查集
模板
```cpp
int gfa(int x)
{
if (fa[x]==x) return x;
fa[x]=gfa(fa[x]);
return fa[x];
}
```
# Part 3
## 例题
#### 修复公路
[题目](https://www.luogu.org/problem/P1111)
最小生成树$Kruskal$模板
```pascal
var
b,c,a,t:array[1..100000] of longint;
n,m,i,k,w,j:longint;
bo:boolean;
procedure sort(l,r: longint);
var
i,j,x,y: longint;
begin
i:=l;
j:=r;
x:=a[(l+r) div 2];
repeat
while a[i]<x do
inc(i);
while x<a[j] do
dec(j);
if not(i>j) then
begin
y:=a[i];
a[i]:=a[j];
a[j]:=y;
y:=b[i];
b[i]:=b[j];
b[j]:=y;
y:=c[i];
c[i]:=c[j];
c[j]:=y;
inc(i);
j:=j-1;
end;
until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
function gfa(x:longint):longint;
begin
if x=t[x] then exit(x);
t[x]:=gfa(t[x]);
exit(t[x]);
end;
begin
readln(n,m);
for i:=1 to n do t[i]:=i;
for i:=1 to m do readln(b[i],c[i],a[i]);
sort(1,m);
for i:=1 to m do
begin
k:=gfa(c[i]);
w:=gfa(b[i]);
if w=k then continue;
t[w]:=t[k];
bo:=true;
for j:=2 to n do
if gfa(j)<>gfa(j-1) then begin bo:=false; break; end;
if bo then begin writeln(a[i]); halt; end;
end;
writeln(-1);
end.
```
#### [NOI2002]银河英雄传说
[题目](https://www.luogu.org/problem/P1196)
并查集带上一个维护
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const int N=30000;
int n,i,x,y,xx,yy,f[N+5],num[N+5],fa[N+5];
char ch;
int gfa(int x)
{
if (x==fa[x]) return x;
int fan=gfa(fa[x]);
f[x]+=f[fa[x]];
fa[x]=fan;
return fa[x];
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for (i=1;i<=N;i++)
fa[i]=i,num[i]=1;
for (i=1;i<=n;i++)
{
cin>>ch>>x>>y;
xx=gfa(x);
yy=gfa(y);
if (ch=='M')
{
f[yy]+=num[xx];
fa[yy]=xx;
num[xx]+=num[yy];
num[yy]=0;
}
if (ch=='C')
{
if (xx!=yy) cout<<-1<<endl;
else cout<<abs(f[y]-f[x])-1<<endl;
}
}
}
```
# Part 4
## 权值并查集
[食物链](https://www.luogu.org/problem/P2024)
```cpp
```