more is better(并查集)

2024-08-23 12:58
文章标签 查集 better

本文主要是介绍more is better(并查集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. Of course there are certain requirements.Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang's selection any two of them who are still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.

输入格式

The first line of the input contains an integer n (0 ≤ n ≤ 100 000) - the number of direct friend-pairs. The following n lines each contains a pair of numbers A and B separated by a single space that suggests A and B are direct friends. (A ≠ B, 1 ≤ A, B ≤ 10000000)

输出

The output in one line contains exactly one integer equals to the maximum number of boys Mr Wang may keep.

样例输入

3
1 3
1 5
2 5
4
3 2
3 4
1 6
2 6

样例输出

4

5


#include <stdio.h>using namespace std;#define N 10000001int Tree[N];int findRoot(int x)
{if(Tree[x] == -1){return x;}else{int tmp = findRoot(Tree[x]);Tree[x] = tmp;return tmp;}
}int sum[N];int main()
{int n,i,a,b;while(scanf("%d",&n) != EOF){for(i = 0;i <= N;i++){Tree[i] = -1;sum[i] = 1;}while(n--){scanf("%d%d",&a,&b);a = findRoot(a);b = findRoot(b);if(a != b){Tree[a] = b;sum[b] += sum[a];}}int ans = 1;for(i = 1;i <= N;i++){if(Tree[i]==-1&&sum[i]>ans){ans = sum[i];}}printf("%d\n",ans);}return 0;
}


这篇关于more is better(并查集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1099446

相关文章

poj 1182 并查集 食物链类

题意: 有n只动物,分别编号1....n。所有动物都属于A,B,C中的一种,已知A吃B,B吃C,C吃A。 按顺序给出下面两种共K条信息: 1. x 和 y 属于同一类。 2. x 吃 y 。 然而这些信息可能会出错,有可能有的信息和之前给出的信息矛盾,也有的信息可能给出的 x 和 y 不在n的范围内。 求k条信息中有多少条是不正确的。 解析: 对于每只动物,创建3个元素 i

POJ1988带权并查集

M u v 将u所在的堆移动到v所在的堆的上面 C u 求u的下面有多少块 带权并查集 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;i

POJ1703带权并查集

D: u v  u与v在不同的集合 A: u v  查询u与v的关系 1)压缩路径过程        fu->root   0  1  u-fu 0                 0  1   1                 1  0 2)合并过程 fu->fv      u->fu   0 1   v->fv 0            1 0 1            0

并查集基础与简单扩展应用

并查集 基础题目路径压缩 扩展应用扩展题目1扩展题目2 并查集的结构是一棵树 并查集有两种功能,一种是判断两个元素是否在同一集合,第二种是合并两个集合 并查集的实现需要记录每个节点的父亲节点 判断两个元素是否在同一集合,即判断两个元素的祖宗节点是否是一个节点(祖宗代表整棵树的根节点) 合并两个集合,即将任意一个集合祖宗的爸爸改为另一个集合的祖宗 基础题目 一共有

nyoj99(并查集+欧拉路+dfs)

单词拼接 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 5 描述 给你一些单词,请你判断能否把它们首尾串起来串成一串。 前一个单词的结尾应该与下一个单词的道字母相同。 如 aloha dog arachnid gopher tiger rat   可以拼接成:aloha.arachnid.dog.gopher.rat.tiger 输入 第一行是一个整

nyoj42(并查集解决欧拉回路)

一笔画问题 时间限制: 3000 ms  |  内存限制: 65535 KB 难度: 4 描述 zyc从小就比较喜欢玩一些小游戏,其中就包括画一笔画,他想请你帮他写一个程序,判断一个图是否能够用一笔画下来。 规定,所有的边都只能画一次,不能重复画。   输入 第一行只有一个正整数N(N<=10)表示测试数据的组数。 每组测试数据的第一行有两个正整数P,Q(P<=1000,Q<

【HDU】5222 Exploration(并查集+拓扑排序)

对于无向边使用并查集合并成一个集合,对于有向边使用判断是否存在环 唯一无语的地方就是看输入是百万级的,加个输入挂跑9s,不加挂跑了5s #include<cstdio>#include<cstring>#include<vector>#include<algorithm>using namespace std;#pragma comment(linker, "/STACK:102

【HDU】How Many Answers Are Wrong(带权并查集)

num[i]代表i到根节点的值 这道题一开始竟然以为是线段树= =!后来发现线段树无法进行子区间的维护 #include<cstdio>#include<cstring>#include<algorithm>using namespace std;const int maxn = 222222;int fa[maxn],num[maxn];int find_father(int

2014级寒假特训之并查集专题

Problem A: Double和XXZ的生日宴请 Time Limit: 1 Sec   Memory Limit: 128 MB Submit: 9   Solved: 7 [ Submit][ Status][ Web Board] [ Edit] [ TestData] Description Double 和 XXZ同一天生日,他们俩30岁生日那天,当年

[论文笔记]Making Large Language Models A Better Foundation For Dense Retrieval

引言 今天带来北京智源研究院(BAAI)团队带来的一篇关于如何微调LLM变成密集检索器的论文笔记——Making Large Language Models A Better Foundation For Dense Retrieval。 为了简单,下文中以翻译的口吻记录,比如替换"作者"为"我们"。 密集检索需要学习具有区分性的文本嵌入,以表示查询和文档之间的语义关系。考虑到大语言模