普通并查集练习

目录

 P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)并查集模板

P1111 修复公路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 排序/联通块

 P1197 [JSOI2008]星球大战逆向并查集/删边/连通块计数

ZOJ3261复杂条件合并操作

 P1396 营救 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)二分答案/并查集处理

 P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)并查集模板

 模板：

#include
using namespace std;
const int N = 1e4;
int pre[N];//每个下标节点的前驱节点
void init(int n) {//初始化
    for (int j = 0; j < n; j++) {
        pre[j] = j;
    }
}
int  find(int x) {//查找祖先
    if (pre[x] == x)return x;
    return pre[x] = find(pre[x]);
//return pre[x]==x?x:pre[x]=find(pre[x]);
}

void com(int a, int b) {//合并操作
    int t1=find(a),t2=find(b);
    if(t1==t1)
        return ;
    if(t1!=t1)//祖先不同，说明不是一个集合的，看情况进行合并
        pre[t1]=t2;
    
}
int is_sm(int x, int y) {//判断两顶点是否是一个集合的
    return find(x) == find(y);
}

int main() {
    int n, m, p;
    cin >> n >> m >> p;
    init(n);//初始化
    for (int j = 1; j <= m; j++) {
        int t1, t2;
        cin >> t1 >> t2;
        com(t1, t2);//合并顶点到同一集合
    }
    for (int j = 1; j <= p; j++) {
        int a, b;
        cin >> a >> b;
        if (is_sm(a, b) == 1)
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
    }
    return 0;
}

P1111 修复公路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 排序/联通块

思路：按路的修复时间排序，如果两顶点没有联通，就修复，合并两顶点，计数器++。修完就说明两村庄相连了。最后判断联通的村庄数量是否==n如果是说明所有村庄都是联通的，反之则不是。

#include 
#include
using namespace std;
const int N=1e5 + 10;
struct node{
    int a,b,t;
}per[N];
int pre[N];
 int n,m;
int fnd(int a){
    return pre[a]==a? a:pre[a]=fnd(pre[a]);
}
int cmp(node a,node b){
return a.t>n>>m;
  for(int j=1;j<=m;j++){
    cin>>per[j].a>>per[j].b>>per[j].t;
  }
  for(int j=1;j<=n;j++){
    pre[j]=j;
  }
    sort(per+1,per+1+m,cmp);
    for(int j=1;j<=m;j++){
        int t1=fnd(per[j].a),t2=fnd(per[j].b);//合并↓
        if(t1!=t2)pre[t1]=t2,n--;
        if(n==1){
        cout< 
Python版本：
 
import copy

class node:
    x,y,t=0,0,0
    def __init__(self,x,y,t):
        self.x=x
        self.y=y
        self.t=t
pre=[]
def init(n):
    for i in range(n+1):
        pre.append(i)
def fnd(x):
    if pre[x]==x:
        return x
    else:
        pre[x]=fnd(pre[x])
        return pre[x]
def join(x,y):
    pre[fnd(y)]=fnd(x)
def judge(x,y):
    if fnd(x)==fnd(y):
        return True
    else:
        return False

n,m=map(int,input().split(' ',2))

l=[]
init(n)
for i in range(m):
    a,b,c=map(int,input().split())
    x=node(a,b,c)
    l.append(copy.deepcopy(x))
l=sorted(l,key=lambda x:x.t)
sum=0
ok=0
for i in range(m):
    t1=fnd(l[i].x)
    t2=fnd(l[i].y)
    if t1!=t2:
        sum=sum+1
        pre[t1]=t2
        if sum==n-1:
            print(l[i].t)
            ok=1
            break
if ok==0:
    print(-1)
 
 P1197 [JSOI2008]星球大战逆向并查集/删边/连通块计数 
 
 思路：删边不可取，离线记录完所有删除的情况，用不会被处理的顶点建立初始的并查集。补顶点同时恢复边，记录连通块个数，但是因为是逆向处理，所以连通块增加时对应的答案应该是减少。
 
#include 
#include
#include
#include
#include
#include
#include
#include
 
 还有个类似的题，但是这题要注意编号等一些细琐但重要的条件
 
ZOJ3261 
 
 
题意：给出n个顶点，每个顶点有对应的能量值，再给出m个顶点对表示初始图的联通情况。
 
最后给出Q个条件，query表示 查询某个顶点所在集合中能量最大的顶点编号（如果最大能量的顶点有相同则输出序号最小的）。destroy+顶点对表示删除该顶点之间的联通。
 
思路：
 
并查集做不到合并完然后删边，所以想到先得到查询数据然后根据删的边逆向并查集，每次删的边变为加上该边，就可以使用合并操作了。既然是逆向离线处理，所以创建初始图的时候如果该边会被删除就不要加入初始图里。
 
最后是合并操作，题目要求输出每个集合中能量最大的顶点，如果能量最大的有多个就输出编号小的，这个条件可以放到并查集合并操作中处理——合并祖先顶点的时候优先把能量值大的顶点当作祖先顶点，小的那个合并进去。如果能量值相同则优先编号小的当作祖先。
  
 
#include 
#include
#include
#include
#include
#include
#include
#include
 
 P1396 营救 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)二分答案/并查集处理 
 
 
题意：题目的问法，最大值最小的情况。很容易想到二分，而要让值最小同时肯定也必须到达目的地。所以二分答案，同时并查集合并比这个值小的所有顶点，最后判断目标起点和终点有没有联通调整二分范围。
 
#include 
#include
using namespace std;
const int N= 2e4  +10;
int pre[N];
int fnd(int a){
    return pre[a]==a?a:pre[a]=fnd(pre[a]);
}
void join(int a,int b){
    int t1=fnd(a),t2=fnd(b);
    if(t1!=t2)
    pre[t1]=t2;
}
int n,m,s,t;
int u[N],v[N],w[N];
int vis[N];
int gra[N][N];
int judge(int a,int b){//判断是否联通
    return fnd(a)==fnd(b);
}
int check(int k){
    for(int j=1;j<=n;j++){
        pre[j]=j;
    }
    for(int j=1;j<=m;j++){
        if(w[j]<=k){
            join(u[j],v[j]);
        }
    }
    return judge(s,t);
}
int main()
{
    cin>>n>>m>>s>>t;
    for(int j=1;j<=m;j++){
        int U,V,W;
        cin>>U>>V>>W;
        u[j]=U;
        v[j]=V;
        w[j]=W;

    }
    int l=-1,r=10001;
    int mid;
    while(l+1!=r){
      mid=(l+r)>>1;
      if(check(mid)){
          r=mid;
      }
      else
          l=mid;
    }
    cout<