簑威龙 发表于 2025-11-30 09:15:05

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

     算法介绍

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

1.P1111 修复公路 - 洛谷

其实就是板子
并查集特征：只关心谁与谁在同一集合
知识点：离线处理
然后就没辣
Talk is cheap,show me the 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;int tot;void add(int u,int v,int tim){    edge[++tot].v=v;    edge.tim=tim;    edge.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=sz;            sz+=sz;            fa=b;      }      else      {            if(find(a)!=find(b))cout

格恳绌 发表于 2025-12-6 11:03:01

yyds。多谢分享

村亢 发表于 2026-1-1 13:41:49

yyds。多谢分享

予捻 发表于 2026-1-17 22:18:48

感谢发布原创作品，程序园因你更精彩

采序 发表于 2026-1-18 00:26:08

过来提前占个楼

昝梓菱 发表于 2026-1-19 02:16:07

热心回复！

梁丘艷蕙 发表于 2026-1-19 04:06:30

这个有用。

史穹逊 发表于 2026-1-20 01:08:12

感谢发布原创作品，程序园因你更精彩

迫蔺 发表于 2026-1-20 20:56:45

喜欢鼓捣这些软件，现在用得少，谢谢分享！

杼氖 发表于 2026-1-21 16:28:21

过来提前占个楼

丘奕奕 发表于 2026-1-21 17:10:30

东西不错很实用谢谢分享

边书仪 发表于 2026-1-21 18:07:17

前排留名，哈哈哈

巨耗 发表于 2026-1-22 05:30:48

这个好，看起来很实用

缀访 发表于 2026-1-22 09:32:12

不错，里面软件多更新就更好了

腥狩频 发表于 2026-1-22 22:09:36

鼓励转贴优秀软件安全工具和文档！

涣爹卮 发表于 2026-1-23 02:55:46

这个好，看起来很实用

贡醮 发表于 2026-1-24 04:27:55

谢谢分享，辛苦了

诞楮 发表于 2026-1-27 14:57:31

分享、互助 让互联网精神温暖你我

掳诚 发表于 2026-2-1 09:35:09

分享、互助 让互联网精神温暖你我

史穹逊 发表于 2026-2-3 13:52:45

东西不错很实用谢谢分享
页: [1] 2
查看完整版本: 云智计划_数据结构_并查集