(模板)并查集

两件事:记得初始化par,以及,路径压缩别写错了…

int par[1005];//记得初始化!
int find(int x)
{
    return par[x]==x?x:par[x]=find(par[x]);//后面这一块不要漏了par[x],否则就是不带路径压缩!
}
bool unite(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return false;
    par[x]=y;
    return true;
}

按秩合并:

int find(int x)
{
    if (x == par[x])
        return x;
    else
        return par[x] = find(par[x]);//后面这一块不要漏了par[x]!!!否则就是不带路径压缩(有时候有用)
}
void unite(int x, int y)
{
    x = find(x); y = find(y);
    if (x == y)
        return;
    if (rank[x] < rank[y]) {
        par[x] = y;
    }
    else {
        par[y] = x;
        if (rank[x] == rank[y])
            rank[x]++;
    }
}
一定要加上:
for(i=1;i<=n;i++){
   par[i]=i;
   }!!!!!!