首页 > 其他分享 >5760: 家庭问题 并查集

5760: 家庭问题 并查集

时间:2023-04-28 17:44:27浏览次数:43  
标签:int 查集 二个 家庭 long find 5760

描述

 

有n个人,编号为1,2,……n,另外还知道存在K个关系。一个关系的表达为二元组(α,β)形式,表示α,β为同一家庭的成员。

当n,k和k个关系给出之后,求出其中共有多少个家庭、最大的家庭中有多少人?

例如:n=6,k=3,三个关系为(1,2),(1,3),(4,5)

此时,6个人组成三个家庭,即:{1,2,3}为一个家庭,{4,5}为一个家庭,{6}单独为一个家庭,第一个家庭的人数为最多。

 

 

输入

 

第一行为n,k二个整数(1≤n≤100)(用空格分隔);

接下来的k行,每行二个整数(用空格分隔)表示关系。

 

 

输出

 

二个整数(分别表示家庭个数和最大家庭人数)。

 

样例输入

 

6 3
1 2
1 3
4 5

样例输出

 3 3

题目来源

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e3+10,inf = 0x3f3f3f3f;
int f[N],a[N]; //f[i]表示i的父亲是谁,a[i]表示i所在的家族人数 
int n,m;
int find(int x)
{
    if(f[x]!=x)f[x] = find(f[x]);
    return f[x];
}
void merger(int x,int y)
{
    int dx = find(x);
    int dy = find(y);
    if(a[dx]<a[dy])swap(dx,dy);
    a[dx]+=a[dy];
    f[dy] = dx;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)f[i] = i,a[i] = 1;
    for(int i=1;i<=m;i++)
    {
        int x,y; cin>>x>>y;
        if(find(x)!=find(y))merger(x,y);
    }
    int cnt = 0,maxx = 0;
    for(int i=1;i<=n;i++)
    {
        if(f[i]==i)
        {
            cnt++;
            maxx = max(maxx,a[i]);
        }
    }
    cout<<cnt<<" "<<maxx;
     return 0;
}

 

标签:int,查集,二个,家庭,long,find,5760
From: https://www.cnblogs.com/jyssh/p/17362818.html

相关文章

  • C语言刷leetcode——并查集
    目录概述参考链接:刷题入门题:547.省份数量(朋友圈)684.冗余连接概述https://leetcode.cn/problems/number-of-provinces/solution/python-duo-tu-xiang-jie-bing-cha-ji-by-m-vjdr/基本概念并查集是一种数据结构并查集这三个字,一个字代表一个意思。并(Union),代表合并查(Find),......
  • 数据结构——并查集
    并查集的作用:可以在近乎O(1)的时间内完成以下两个操作1、将两个集合合并2、询问两个元素是否在一个集合中 基本原理:用“树”的形式来维护每一个集合,树根的编号就是整个集合的编号,每个结点存储它的父结点(如:p[x]表示x的父结点)问题1:如何判断树根?  A:if(p[x]==x),当前x就是......
  • 并查集の进阶用法
    普通并查集我们在处理问题的时候,可能会遇到一些需要维护每个元素所在的集合的问题,而并查集却恰好完美解决了这个问题。对于普通的并查集,他支持的操作比较少,只有合并和查询,合并是指把两个集合合并成一个,而查询是询问两个元素是否在同一集合内;对于这两种操作,我们可以用一个数组\(......
  • 并查集
    并查集并查集是一种用于管理元素所属集合的数据结构,实现为一个森林,其中每棵树表示一个集合,树中的节点表示对应集合中的元素合并(Union):合并两个元素所属集合(合并对应的树)查询(Find):查询某个元素所属集合(查询对应的树的根节点),这可以用于判断两个元素是否属于同一集合importjava.u......
  • hdu 5441 长春区域赛网络赛 1005 Travel(并查集)
    题目链接:hdu5441题目大意:有一个n个点的无向图,给出m条边的边权,给出q次询问,每次给出一个值,求用到所有边权不大于这个值的边的情况下,能够互相到达的点对的个数(自己到自己不算)题目分析:首先我们对于边按照边权从小到大排序,对于询问按照值从小到大排序。枚举每次询问,从前到后扫描边,如果......
  • 并查集及其扩展(附例题与完整讲解cpp)
    文章目录基础并查集1.P1551亲戚2.P1536村村通种类并查集1.P1892[BOI2003]团伙2.P1525[NOIP2010提高组]关押罪犯3.P2024[NOI2001]食物链带权并查集基础并查集并查集就是用来维护一些元素之间的关系的集合。例如A的亲戚是B,则我们可以把A与B放到同一个集合中,表示AB属......
  • 良心发现?启智协会欲做家庭代工,竟遭诈骗人员诚实劝退!Alpe Market未经FCA授权遭警告
    最近由于全球经济动荡,物价随着货币通膨持续上涨,许多人因此寻找其他投资或兼职的机会,而诈骗集团也乘机在网络上发布虚假的工作职缺,以此骗取民众的金钱与个资。不过上周有网友分享自己被诈骗人员劝退的趣事。4/11,一位女网友在脸书社团「爆怨公社」发文,表示自己最近在为启智协会的学员......
  • N1・N2听力单词 —— 交通、出行 / 家庭生活、人际关系
    一、N2見学(けんがく):参观学习見物(けんぶつ):游览、观赏、游客;見物(みもの):值得一看的东西、事情,有看的价值観光コース:观光路线(コース:course)格安(かくやす):特价,特别便宜レンタカー:租赁车(rentacar)寝台車(しんだいしゃ):卧铺车ホーム:platform,月台改札口(かいさつぐち):检票口モノレール:monorail,......
  • 团体天梯练习 L2-007 家庭房产
    L2-007家庭房产给定每个人的家庭成员和其自己名下的房产,请你统计出每个家庭的人口数、人均房产面积及房产套数。输入格式:输入第一行给出一个正整数$N(≤1000)$,随后N行,每行按下列格式给出一个人的房产:编号父母\(k\)孩子1...孩子\(k\)房产套数总面积其中编号是每个......
  • 23-4-15--并查集--部落
    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不相交的部落?并且检查任意两个人是否属于同一个部落。输入格式:输入在第一行给出一个正整数N(≤104),是已知小圈子的个数......