普通并查集练习

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)

 思路：删边不可取，离线记录完所有删除的情况，用不会被处理的顶点建立初始的并查集。补顶点同时恢复边，记录连通块个数，但是因为是逆向处理，所以连通块增加时对应的答案应该是减少。

#include 
#include
#include
#include
#include
#include
#include
#include

 还有个类似的题，但是这题要注意编号等一些细琐但重要的条件

题意：给出n个顶点，每个顶点有对应的能量值，再给出m个顶点对表示初始图的联通情况。

最后给出Q个条件，query表示 查询某个顶点所在集合中能量最大的顶点编号（如果最大能量的顶点有相同则输出序号最小的）。destroy+顶点对表示删除该顶点之间的联通。

思路：

并查集做不到合并完然后删边，所以想到先得到查询数据然后根据删的边逆向并查集，每次删的边变为加上该边，就可以使用合并 *** 作了。既然是逆向离线处理，所以创建初始图的时候如果该边会被删除就不要加入初始图里。

最后是合并 *** 作，题目要求输出每个集合中能量最大的顶点，如果能量最大的有多个就输出编号小的，这个条件可以放到并查集合并 *** 作中处理——合并祖先顶点的时候优先把能量值大的顶点当作祖先顶点，小的那个合并进去。如果能量值相同则优先编号小的当作祖先。
 

#include 
#include
#include
#include
#include
#include
#include
#include

题意：题目的问法，最大值最小的情况。很容易想到二分，而要让值最小同时肯定也必须到达目的地。所以二分答案，同时并查集合并比这个值小的所有顶点，最后判断目标起点和终点有没有联通调整二分范围。

#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<