云智计划_数据结构_并查集

     算法介绍

其实没什么好说的
注意几个点
1.fa=i;
2.按秩合并(亦称启发式合并)与路径优化可以同时存在，只有一个复杂度为O(nlog n)，两个都用就是O(nα(n))，相当于O(n)
α()在1e6的数据下，也只有5，比常数还常数
代码
int find(int x){return(fa[x]==x?x:fa[x]=find(fa[x]));}

1. void marge(int a,int b)
2. {
3.     x=find(x);y=find(y);
4.     if(a==b)return ;
5.     else fa[a]=b;//实在复杂度就是差一点，可以写个按秩排序
6. }

复制代码

 基础例题

1.P1111 修复公路 - 洛谷

其实就是板子
并查集特征：只关心谁与谁在同一集合
知识点：离线处理
然后就没辣
Talk is cheap,show me the code[code]//https://www.luogu.com.cn/problem/P1111//P1111 修复公路#include#include#define maxm 100010#define maxn 1010using namespace std;struct EDGE{    int u,v,tim;}edge[maxm];int tot;void add(int u,int v,int tim){    edge[++tot].v=v;    edge[tot].tim=tim;    edge[tot].u=u;}bool rule(EDGE a,EDGE b){    return a.tim>n>>m;    for(int i=1;i>x>>y>>z;        add(x,y,z);    }    sort(edge+1,edge+tot+1,rule);    for(int i=1;i>a.y>>a.relation;        //*+*+*+*+*+*+*离散化Discretization*+*+*+*+*+*+*        for(int i=1;ia>>b;        if(c=='M')        {            a=find(a);            b=find(b);            tag[a]=sz;            sz+=sz[a];            fa[a]=b;        }        else        {            if(find(a)!=find(b))cout

yyds。多谢分享