加边的无向图（并查集）

并查集的裸体
问加几条边可以使图中的点两两到达就是使图成为连通图
也就是说所有点的根节点都指向一个点
用数组p[j]记录j节点的根节点
也就是说对于所有的点 有且仅有一个点的 p[i]=i， 也就是唯一的父亲节点

如果有两个就说明图中有两个连通块 也就是需要 一条边取联通这两个块
以此类推
代码

#include <map>
#include <set>
#include <cmath>
#include <stack>
#include <queue>
#include <cstdio>
#include <bitset>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#define UpMing main
#define re register
#pragma GCC optimize(2)
#define Accept return 0;
#define lowbit(x) ((x)&(-(x)))
#define mst(x, a) memset( x,a,sizeof(x) )
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define dep(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
const int inf =0x3f3f3f3f;
const int maxn=5e5+7;
const ll mod = 1e9+7;
const int N =1e6+3;
inline ll read() {
    ll  x=0;
    bool f=0;
    char ch=getchar();
    while (ch<'0'||'9'<ch)    f|=ch=='-', ch=getchar();
    while ('0'<=ch && ch<='9')
        x=x*10+ch-'0',ch=getchar();
    return f?-x:x;
}
void out(ll x) {
    int stackk[20];
    if(x<0) {
        putchar('-');
        x=-x;
    }
    if(!x) {
        putchar('0');
        return;
    }
    int top=0;
    while(x) stackk[++top]=x%10,x/=10;
    while(top) putchar(stackk[top--]+'0');
}
ll n,m,p[maxn],ans;
ll find(ll x) {
    if(p[x]==x) return x;
    return p[x]=find(p[x]);
}
void combine(ll x,ll y) {
    ll dx=find(x);
    ll dy=find(y);
    if(dx!=dy)
        p[dx]=dy;
}
int UpMing() {
    n=read();
    m=read();
    for(int i=1 ; i<=n ; i++) p[i]=i;
    while(m--) {
        ll x=read();
        ll y=read();
        combine(x,y);
    }
    for(int i=1 ; i<=n ; i++) {
        if(p[i]==i) ans++;
    }
    out(ans-1);
    Accept;
}