并查集的基本操作

$init（）$初始化操作，构建一群根作为自己的森林。
$find（）$查找操作，注意路径压缩（就是把链式结构转化为树状图）
$unionset（）$合并操作，将两个元素对应的集合进行合并 $pre[find(x)]=find(y)$

最后是记录根节点个数的操作，也就是不同的集合个数。
$if (pre[i]==i) cnt++;$

//推荐find模板
int find(int x){
    if(pre[x] != x) pre[x] = find(pre[x]);
    return pre[x];
} 

int find(int x) {//路径压缩 查找集合的根节点 
    return x==pre[x]?x:pre[x]=find(pre[x]);
}
/*      1
      2   3
    4  5 

*/
pre[4]=find(2);
pre[2]=find(1);
pre[1]=1;(一层层回溯上去) 

P3367 【模板】并查集

#include<bits/stdc++.h>
using namespace std;

int pre[10005];

void init(int n){//每个点就是一个独立的集合，每个都是根节点 
    for(int i=1;i<=n;i++)
        pre[i]=i;
}

int find(int x) {//路径压缩 查找集合的根节点 
    return x==pre[x]?x:pre[x]=find(pre[x]);
}

int main(){
    int n,m;
    cin>>n>>m;
    init(n);
    while(m--){
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1) pre[find(x)]=find(y);//把集合合并 
        else {
            if(find(x)==find(y)) cout<<"Y"<<endl;
            else cout<<"N"<<endl;
         }

     }

    return 0;
}

例题小试

 题意分析：将距离小于等于d的点看作是一个集合
           用并查集算法讲距离小于等于d的点合并到一个集合中
           最后输出所有集合的个数
     注意：把坐标的位置作为独立的集合，
           和坐标没有关系，坐标只是判断是否属于同一个集
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e5+10;

int pre[maxn],x[maxn],y[maxn];
int Find(int x) {
    return x==pre[x]?x:pre[x]=Find(pre[x]);
}
int main() {
    int n,m;
    cin>>n>>m;
    for (int i=1; i<=n; i++) cin>>x[i]>>y[i],pre[i]=i;
    for (int i=1; i<=n; i++) {
        for (int j=i+1; j<=n; j++) {
            if ((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=m*m) {
                int u=Find(i),v=Find(j);
                if (u!=v) pre[u]=v;
            }
        }
    }
    int cnt=0;
    for (int i=1; i<=n; i++) {
        pre[i]=Find(pre[i]);
        if (pre[i]==i) cnt++;
    }
    cout<<cnt;
    return 0;
} 

畅通工程

#include<bits/stdc++.h>
using namespace std;
int n,m,pre[1005];

int find(int x) {//路径压缩 查找集合的根节点 
   if(pre[x]!=x) pre[x]=find(pre[x]);
   return pre[x];
}

int main(){
    while(cin>>n>>m) {
    if(n==0) break;
    for(int i=1;i<=n;i++) 
    pre[i]=i;
   for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        int x=find(u);
        int y=find(v);
        if(x!=y) pre[x]=y;
    }
    int ans=0;
    for(int i=1;i<=n;i++) 
        if(pre[i]==i) ans++;
    cout<<ans-1<<endl;

    }
}

继续畅通工程

题意：关键是cmp排序（按照是否修建再金额大小排序）
       排序完判断是否是同一个父结点
       再把两条公路间进行合并 每合并一次就加一次金额

#include <bits/stdc++.h>
using namespace std;
int pre[110];

struct node{
    int x,y,c,d;
}a[110];

bool cmp(node a,node b){
    if(a.d!=b.d) return a.d>b.d;
    return a.c<b.d;
}
int find(int x){
    if(pre[x]!=x) pre[x]=find(pre[x]);
    return pre[x];
}

int main(){
    int n;
    while(cin>>n){
        if(n==0) break;
        for(int i=1;i<=n;i++) pre[i]=i;
        int m=n*(n-1)/2;
        for(int i=0;i<m;i++)
            cin>>a[i].x>>a[i].y>>a[i].c>>a[i].d;
        sort(a,a+m,cmp);
        int sum=0;
        for(int i=0;i<m;i++){
            int t1=find(a[i].x);
            int t2=find(a[i].y);
            if(t1!=t2) {
                pre[t2]=t1;//联通两个村庄
                if(a[i].d==0) sum+=a[i].c;
            }

        }
        cout<<sum<<endl;
    }
} 

畅通工程之最低成本建设问题

 题意： 1、Kruskal算法 (用并查集判断是否会出现环的选取) 
        2、Prim算法    (每次找到最小边权,进行标记,依次更新边权值) 
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e5+10;
int pre[N];
struct node{
    int a,b,w;
}x[N];

bool cmp(node x,node y){//边从小到大排序 
    return x.w<y.w;
}
int find_(int x){
    if(x!=pre[x]) pre[x] = find_(pre[x]);
    return pre[x];
}

void Kruskal(){
    int sum = 0,cnt =0;
    for(int i=1;i<=n;i++) pre[i] = i;
    sort(x+1,x+n+1,cmp);
    for(int i=1;i<=n;i++){
        int t1 = find_(x[i].a);
        int t2 = find_(x[i].b);
        if(t1!=t2){
            pre[t1] = t2;
            sum+=x[i].w;
            cnt++;
        }
    }
    if(cnt == m-1) cout<<sum<<endl;
    else cout<<"?"<<endl; 
}
int main(){
    while(scanf("%d %d",&n,&m)==2){
        if(n==0) break;
        for(int i=1;i<=n;i++) cin>>x[i].a>>x[i].b>>x[i].w;
        Kruskal();
    }
    return 0;
}
/*
3 3
1 2 1
1 3 2
2 3 4
1 3
2 3 2
0 100
*/

小希的迷宫

题意：输出No的情况有：回路中形成环（输入的两个点已经在一个集合里）
                       边长数不是顶点-1
注意：0 0也会输出yes
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
int n,pre[maxn];
bool m[maxn];

int find(int x){
    if(pre[x]!=x) pre[x]=find(pre[x]);
    return pre[x];
}

int main(){
    while(1){
        memset(m,0,sizeof(m));//标记端点是否被使用 
        int a,b;
        int num=0,ans=0;
        int flag=1;
        for(int i=1;i<=maxn;i++) pre[i]=i;
        while(cin>>a>>b){
            if(a==0 && b==0) break;
            if(a==-1 && b==-1) return 0;
            if(a==b) continue;
            int x=find(a);
            int y=find(b);
            if(x==y) flag=0;
            else {
                pre[x]=y;
                ans++;
            }
                if(!m[a]) m[a]=1,num++;
                if(!m[b]) m[b]=1,num++;

        }
        if((num-1!=ans && ans ) || flag==0) 
        puts("No");
        else puts("Yes");
    }
    return 0;
}

map+并查集

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
int fa[maxn];
int id[maxn];
map<long long,int> mp;

int find(int x) {
    return x==fa[x]?x:fa[x]=find(fa[x]);
}

void merge(int x,int y)
{
    x = find(x);
    y = find(y);
    if(x == y)
        return;
    fa[x] = y;
}

int main()
{
    int n,a,b,z,q;
    scanf("%d%d%d%d%d",&n,&a,&b,&z,&q);
    for(int i = 1;i<=n;i++){
        long long x;
        fa[i] = i;
        scanf("%lld",&x);
        mp[x] = i;
    }
    for(int i = 1;i<=a;i++){
        long long x;
        scanf("%lld",&x);
    }
    for(int i = 1;i<=b;i++){
        long long x;
        scanf("%lld",&x);
        merge(0,mp[x]);
    }
    for(int i = 1;i<=z;i++){
        long long u,v;
        scanf("%lld%lld",&u,&v);
        merge(mp[u],mp[v]);
    }
    while(q--){
        long long x;
        scanf("%lld",&x);
        if(find(mp[x]) == find(0)){
            printf("wa\n");
        }
        else printf("ac\n");
    }
    return 0;
}