写点什么

2021-11-27【算法竞赛入门到进阶】

  • 2022 年 5 月 03 日
  • 本文字数:876 字

    阅读完需:约 3 分钟

例如加入第 1 个朋友关系(1,2),在并查集 s s s 中,把结点 1 合并到结点 2,也就是把结点 1 的集 1 改正为集 2。

[](()(3)查找

查找元素的集是一个递归的过程,直到元素的值和它的集相等就找到了根节点的集。但是,当搜索树的高度很大时,复杂度是 O ( n ) O(n) O(n) 的,变成了一个链表,出现了数的“退化”现象。

[](()(4)统计有多少个集

如果s[i]=i,这就是一个根节点,是它所在的集的代表;统计根节点的数量,就是集的数量。


下面以 h d u 1213 hdu 1213 hdu1213 为例实现操作

[](()题目描述:

[How Many Tables](()


问题描述


今天是伊格内修斯的生日。他邀请了很多朋友。现在是晚餐时间。 Ignatius 想知道他至 《一线大厂 Java 面试题解析+后端开发学习笔记+最新架构讲解视频+实战项目源码讲义》无偿开源 威信搜索公众号【编程进阶路】 少需要多少张桌子。你要注意,并不是所有的朋友都互相认识,所有的朋友都不想和陌生人呆在一起。


这个问题的一个重要规则是,如果我告诉你 A 认识 B,B 认识 C,这意味着 A、B、C 彼此认识,所以他们可以留在一张桌子上。


例如:如果我告诉你 A 认识 B,B 认识 C,D 认识 E,那么 A、B、C 可以留在一张桌子上,而 D、E 必须留在另一张桌子上。所以伊格内修斯至少需要 2 张桌子。


输入


输入以整数 T(1<=T<=25) 开头,表示测试用例的数量。然后是 T 测试用例。每个测试用例以两个整数 N 和 M(1<=N,M<=1000) 开始。 N 表示好友的数量,好友从 1 到 N 标记,然后是 M 行。每行由两个整数 A 和 B(A!=B) 组成,这意味着朋友 A 和朋友 B 彼此认识。两个案例之间会有一个空行。


输出


对于每个测试用例,只需输出 Ignatius 至少需要多少张表。不要打印任何空白。


#include<bits/stdc++.h>


using namespace std;


const int maxn = 1050;


int s[maxn + 1];


void init(){


for (int i = 1; i <= maxn;i++){


s[i] = i;


}


}


int find(int x){


return x == s[x] ? x : find(s[x]);


}


void common(int x,int y){


x = find(x);


y = find(y);


if(x!=y)


s[x] = s[y];


}


int main(){


int t, n, m, x, y;


cin >> t;


while(t--){


cin >> n >> m;


init();


for (int i = 1; i <= m;i++){


cin >> x >> y;


common(x, y);


}


int ans = 0;

用户头像

还未添加个人签名 2022.04.13 加入

还未添加个人简介

评论

发布
暂无评论
2021-11-27【算法竞赛入门到进阶】_程序员_爱好编程进阶_InfoQ写作社区