首页 > 其他分享 >洛谷题单指南-集合-P1536 村村通

洛谷题单指南-集合-P1536 村村通

时间:2024-03-20 11:58:13浏览次数:25  
标签:P1536 return int 洛谷题 城镇 集合 find 村村通

原题链接:https://www.luogu.com.cn/problem/P1536

题意解读:城镇之间现有的道路关系可以将城镇划分的若干集合,每个集合内的城镇是互通的,要计算最少增加多少条道路,使得每个集合都相通。

解题思路:

利用并查集,统计一共出现多少个集合,即p[i] = i的数量,

最少的道路数即集合数-1,即可把所有集合“串”起来,使得所有城镇可以互通。

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1005;

int p[N], n, m;

int find(int x)
{
    if(p[x] == x) return x;
    return p[x] = find(p[x]);
}

void merge(int x, int y)
{
    p[find(x)] = find(y);
}

int main()
{
    int i, j;
    while(cin >> n && n != 0)
    {
        cin >> m;
        for(int i = 1; i <= n; i++) p[i] = i; //多组数据,每次都要对并查集初始化
        while(m--)
        {
            cin >> i >> j;
            merge(i, j);
        }
        int ans = 0;
        for(int i = 1; i <= n; i++)
        {
            if(p[i] == i) ans++; //p[i] = i的即根节点,也就是集合的编号
        }
        cout << ans - 1 << endl;
    }

    return 0;
}

 

标签:P1536,return,int,洛谷题,城镇,集合,find,村村通
From: https://www.cnblogs.com/jcwy/p/18084906

相关文章

  • 洛谷题单指南-集合-P1551 亲戚
    原题链接:https://www.luogu.com.cn/problem/P1551题意解读:要判断两人是否是亲戚,只需要看两人是否属于一个集合,基于所有已知的亲戚关系,可以建立多个有亲戚关系的集合,这个过程可以借助并查集。解题思路:并查集:1、定义并查集是一种树形数据结构,本质上是多棵树,每棵树表示一个集合,......
  • 洛谷题单指南-二叉树-P1185 绘制二叉树
    原题链接:https://www.luogu.com.cn/problem/P1185题意解读:在表格中绘制二叉树,有几个关键点1、结点用小写字母o 表示,对于一个父亲结点,用 / 连接左子树,用 \连接右子树,表格其余地方填空格。2、第m层结点若两个属于同一个父亲,那么它们之间由 3个空格隔开;若两个结点相邻但......
  • 洛谷题单指南-二叉树-P3884 [JLOI2009] 二叉树问题
    原题链接:https://www.luogu.com.cn/problem/P3884题意解读:要计算二叉树的深度、宽度、节点间的距离,深度、宽度的概念很好理解,节点间的距离描述是:节点u,v之间的距离表示从u到v的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。说人话就是:u到v的距离=uv最近公共祖先到u......
  • 洛谷题解 - B3850 [GESP202306 四级] 幸运数
    目录题目描述输入格式输出格式样例#1样例输入#1样例输出#1代码题目描述小明发明了一种“幸运数”。一个正整数,其偶数位不变(个位为第111位,十位为第......
  • 洛谷题单指南-二叉树-P1030 [NOIP2001 普及组] 求先序排列
    原题链接:https://www.luogu.com.cn/problem/P1030题意解读:已知中序、后序,求先序。解题思路:与洛谷题单指南-二叉树-P1827[USACO3.4]美国血统AmericanHeritage非常类似,不在介绍过程,直接给出代码。100分代码:#include<bits/stdc++.h>usingnamespacestd;stringin,post......
  • 村村通(P1536)
    #include<bits/stdc++.h>#defineendl'\n'usingll=longlong;typedefunsignedlonglongull;usingnamespacestd;voidGordenGhost();map<int,int>fa;intfindB(intx){if(fa[x]==x)returnx;returnfa[x]=findB(fa[x]);}......
  • 洛谷题单指南-二叉树-P5076 【深基16.例7】普通二叉树(简化版)
    原题链接:https://www.luogu.com.cn/problem/P5076题意解读:此题本质上是要实现一个二叉搜索树的功能。解题思路:从数据规模10^4来看,只要复杂度在n^2范围内基本上是可以通过的,下面给出两种做法:1、有序数组法对应5个操作的实现逻辑如下:操作一:查x的排名。直接通过二分查找>=x的第......
  • 洛谷题单指南-二叉树-P4913 【深基16.例3】二叉树深度
    原题链接:https://www.luogu.com.cn/problem/P4913题意解读:计算二叉树的深度解题思路:首先介绍二叉树的存储方式,对于本题,直接用数组模拟,数组的下标即节点号structnode{intl,r;}tree[N];tree[i].l存的是节点i的左子结点,tree[i].r存的是节点i的右子节点。计算深度至......
  • 洛谷题单指南-二叉树-P4715 【深基16.例1】淘汰赛
    原题链接:https://www.luogu.com.cn/problem/P4715题意解读:计算亚军得主,注意能力值最高的肯定是冠军,但能力值第二高的不一定是亚军,因为有可能中途就遭遇冠军。解题思路:根据题意,两两比赛,一轮后再按顺序两两比赛,形如一棵二叉树,但解题其实用不到二叉树的数据结构可以看出,最后参与......
  • 洛谷题单指南-线性表-P2234 [HNOI2002] 营业额统计
    原题链接:https://www.luogu.com.cn/problem/P2234题意解读:要计算每一天最小波动值的和,需要对每一天求最小波动值,再求和,如果暴力法,时间复杂度在1+2+3+......+32767≈5*10^8,可能会超时。解题思路:1、暴力法:由于本题测试数据比较水,实测暴力求解直接可以AC,由于没有技术含量,不做具体......