并查集 hdu 1232

骑猪看日落 2022-08-23 11:54 118阅读 0赞

/*hdu 1232 并查集*/
    # include<iostream>
    # include<cstdio>
    # include<cstring>
    # include<algorithm>
    # include<cstdlib>
    # include<cmath>
    using namespace std;
    int bin[1008];
    int findx(int x)//并查集中的压缩路径的方法，可以大大减少时间的复杂度
    {
     if(x!=bin[x])
        bin[x]=findx(bin[x]);//运用了递归的思想
      return bin[x];
    }
    void merge(int x,int y)//合并集合的函数
    {
        int fx,fy;
        fx=findx(x);
        fy=findx(y);
        if(fx>fy)
            bin[fx]=fy;
        else
            bin[fy]=fx;
    }
    int main()
    {
        int n,m;
        int a,b;
        while(cin>>n)
        {
            if(n==0) break;
            cin>>m;
            for(int i=1;i<=n;i++)//这步是给父亲节点进行初始化
            {
                bin[i]=i;
            }
            while(m--)
            {
                cin>>a>>b;
                merge(a,b);
            }
            int count=0;
            for(int i=1;i<=n;i++)
            {
                if(bin[i]==i) count++;
            }
            cout<<count-1<<endl;//这里减1是因为在初始化时，已经bin[i]=i在其中，最少有1个符合要求
        }
        return 0;
    }
    /*
    总结体会：
    对于一个算法，个人觉得最主要是它的作用，而此处并查集的作用就是：
    判断图和树的连通性以及衍生出来的连通分支数的计算；
    并查集具体算法思想还是很容易上手的，还有就是其中有个压缩路径的优化操作
    运用递归的思想，这个还是值得去体会一下，也许可能很简单，但是不要仅仅局限在一道题目上，
    要做到一通百通。
    */

发表评论取消回复

表情：

评论列表（有 0 条评论，118人围观）

还没有评论，来说两句吧...

相关阅读

相关并查集 Hdu 1272 (判环)+ Hdu 1213 + Hdu 1232 + Hdu 3172

Hdu 1272 小希的迷宫思路：两点的根节点相同，并且他们又彼此连通，则说明构成环。如果无环且点数-1==边数则说明只有一个连通块 include <cst

我不是女神ヾ/ 2022年09月20日 15:09/ 0 赞/ 204 阅读

相关 HDU 1232（最小生成树；并查集）

题意：如题。最小生成树建模方法：已有的边的花费为0，不存在的边花费为1，求最小生成树。 include<cstdio> include

淩亂°似流年/ 2022年09月20日 11:28/ 0 赞/ 191 阅读

相关并查集 hdu 1232

/hdu 1232 并查集/ include<iostream> include<cstdio> include<cstring>

骑猪看日落/ 2022年08月23日 11:54/ 0 赞/ 119 阅读

相关 hdoj 1232 畅通工程【并查集】

畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Othe

た入场券/ 2022年08月04日 11:43/ 0 赞/ 172 阅读

相关畅通工程--hdu1232(并查集)

畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Love The Way You Lie/ 2022年08月04日 08:54/ 0 赞/ 196 阅读

相关 Hdu 1232 畅通工程（并查集水题）

题目：畅通工程 Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

拼搏现实的明天。/ 2022年06月10日 12:23/ 0 赞/ 169 阅读

相关 HDU 1232 畅通工程 (并查集)

//题意不会度娘，用BOSS代替路 include <stdio.h> include <string.h> int a[1050];

偏执的太偏执、/ 2022年06月05日 01:55/ 0 赞/ 201 阅读

相关并查集-HDU 1232-畅通工程

并查集-HDU 1232-畅通工程 -------------------- 题目链接：[畅通工程][Link 1] 并查集基础： [数据

绝地灬酷狼/ 2022年05月15日 01:56/ 0 赞/ 246 阅读

相关 HDU-1232.畅通工程(并查集)

[HDU-1232.畅通工程][HDU-1232.] Problem Description 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连

港控/mmm°/ 2022年03月09日 05:58/ 0 赞/ 222 阅读

相关 hdu1232 畅通工程【并查集】超详细题解

目录 1.题目 2.题意 3.思路 4.代码 1.题目某省

约定不等于承诺〃/ 2021年07月24日 21:08/ 0 赞/ 439 阅读