ACM模版——并查集

简介: ACM模版——并查集

注释版:

/* 普通版(无路径压缩) */
int pre[1000];
int find(int x)                // 查找我(x)的掌门
{
    int r=x;                   // 委托 r 去找掌门
    while(pre[r]!=r)           // 如果r的上级不是r自己(也就是说找到的大侠他不是掌门 = =)
    r=pre[r];                  // r 就接着找他的上级,直到找到掌门为止。
    return r;                  // 掌门驾到~
}
/* 升级版(有路径压缩) */
int pre[1000];
int find(int x)                     // 查找根节点
{ 
    int r=x;
    while( pre[r]!= r )             // 返回根节点 r
         r=pre[r];
    int i=x, j;
    while( i != r )                 // 路径压缩
    {
         j = pre[i];        // 在改变上级之前用临时变量 j 记录下他的值 
         pre[i] = r ;         // 把上级改为根节点
         i = j;
    }
    return r ;
}
void join(int x,int y)             // 我想让虚竹和周芷若做朋友
{
    int fx=find(x),fy=find(y);     // 虚竹的老大是玄慈,芷若MM的老大是灭绝
    if(fx!=fy)                     // 玄慈和灭绝显然不是同一个人
        pre[fx]=fy;                    // 方丈只好委委屈屈地当了师太的手下啦,注意这里谁是谁的root,以及这里是 x 的祖先成为 fy 的子孙,而不是 x 成为 fy 的子孙
}

简化版:    

int pre[1000];
int find(int x) // 普通最简版
{
    return pre[x]==x ? x : pre[x]=find(pre[x]);
}
int find(int x) // 优化版                    
{ 
    int r=x;
    while( pre[r]!= r )            
         r=pre[r];
    int i=x, j;
    while( i != r )                 
    {
         j = pre[i];        
         pre[i] = r ;         
         i = j;
    }
    return r ;
}
void join(int x,int y)             
{
    int fx=find(x),fy=find(y);     
    if(fx!=fy)                     
        pre[fx]=fy;                    
}

应用:

/* 统计 root 结点个数(必要时适当修改) */
int cnt=0;
for(int i=1;i<=n;i++) 
    if(pre[i]==i) // 有局限性,前提确保在 n 的范围内,而且一定会出现[1,n]
        cnt++;
/* 统计每个 root 的内部总数(必要时适当修改) */
int rs=0;
for(int i=1;i<=n;i++)
{
    int rt=find(i);
    vis[rt]++;
    rs=max(rs,vis[rt]);
}

常见问题:

  1. 并查集中,不能参与统计 / 运算操作,因为会出现中途连接之前断开的结点,这样之前的计算就会有误差,所以要并查集完了之后,再做这类操作。
目录
相关文章
|
2天前
|
弹性计算 人工智能 安全
云上十五年——「弹性计算十五周年」系列客户故事(第二期)
阿里云弹性计算十五年深耕,以第九代ECS g9i实例引领算力革新。携手海尔三翼鸟、小鹏汽车、微帧科技等企业,实现性能跃升与成本优化,赋能AI、物联网、智能驾驶等前沿场景,共绘云端增长新图景。
|
8天前
|
存储 弹性计算 人工智能
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
2025年9月24日,阿里云弹性计算团队多位产品、技术专家及服务器团队技术专家共同在【2025云栖大会】现场带来了《通用计算产品发布与行业实践》的专场论坛,本论坛聚焦弹性计算多款通用算力产品发布。同时,ECS云服务器安全能力、资源售卖模式、计算AI助手等用户体验关键环节也宣布升级,让用云更简单、更智能。海尔三翼鸟云服务负责人刘建锋先生作为特邀嘉宾,莅临现场分享了关于阿里云ECS g9i推动AIoT平台的场景落地实践。
【2025云栖精华内容】 打造持续领先,全球覆盖的澎湃算力底座——通用计算产品发布与行业实践专场回顾
|
7天前
|
人工智能 自然语言处理 自动驾驶
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
关于举办首届全国大学生“启真问智”人工智能模型&智能体大赛决赛的通知
|
6天前
|
云安全 人工智能 自然语言处理
阿里云x硅基流动:AI安全护栏助力构建可信模型生态
阿里云AI安全护栏:大模型的“智能过滤系统”。
|
7天前
|
编解码 自然语言处理 文字识别
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
凌晨,Qwen3-VL系列再添新成员——Dense架构的Qwen3-VL-8B、Qwen3-VL-4B 模型,本地部署友好,并完整保留了Qwen3-VL的全部表现,评测指标表现优秀。
618 7
Qwen3-VL再添丁!4B/8B Dense模型开源,更轻量,仍强大
|
10天前
|
存储 机器学习/深度学习 人工智能
大模型微调技术:LoRA原理与实践
本文深入解析大语言模型微调中的关键技术——低秩自适应(LoRA)。通过分析全参数微调的计算瓶颈,详细阐述LoRA的数学原理、实现机制和优势特点。文章包含完整的PyTorch实现代码、性能对比实验以及实际应用场景,为开发者提供高效微调大模型的实践指南。
734 2