毛豆

用户名：liuyt

访问量：14711

签　名：

等　　级
排　　名	1089
经　　验	3090
参赛次数	3
文章发表	34
年　　龄	22
在职情况	学生
学　　校	燕山大学
专　　业	计算机

　　自我简介：

TA的其他文章

动态规划之最长公共子序列问题 C++实现
浏览：478

递归的使用
浏览：743

队列简化问题
浏览：382

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

肺炎大作战-题解(C++代码)

　　作者: 毛豆　　　　发表时间：2020-04-30 09:38:19 浏览：175　|　评论：1　

原题链接：肺炎大作战

一个简单的并查集，本题抽象为求并查集最大群体的问题，
只需要在并查集的基础上开一个额外的计数数组，
最后遍历一遍找出最大群体即可

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int MAXN = 100011;
int N;
int x,y;
int MaxId,MaxNum,Num[MAXN],Father[MAXN];
void Initial()
{
	MaxId = MaxNum = -1;
	for(int i = 0;i < MAXN;i++)
		Father[i] = i,Num[i] = 1;//Num数组的元素都初始化为 1,最少有一个人 
}
int Find(int x)
{
/*	if(x != Father[x])
		Father[x] = Find(Father[x]);
	return Father[x];
*/
	return x == Father[x] ? Father[x] : Father[x] = Find(Father[x]);
}
void Union(int x,int y)
{
	x = Find(x);
	y = Find(y);
	if(x != y)
		Father[x] = y,Num[y] += Num[x];//合并的同时将人数加到根节点上,这里要注意,不要写反了 
}
int main()
{
	while(~scanf("%d",&N))
	{
		if(!N)
		{
			printf("1\n");
			continue;
		}
		Initial();
		while(N--)
		{
			scanf("%d%d",&x,&y);
			//这里求出出现过的id最大为MaxId,因为这里是千万的数量级,全部循环一次会耗费较多的时间 
			if(MaxId < x)MaxId = x;
			if(MaxId < y)MaxId = y;
			Union(x,y);
		}
		for(int i = 0;i <= MaxId;i++)//找出最大的人数
			if(MaxNum < Num[i])
				MaxNum = Num[i];
		printf("%d\n",MaxNum);
	}
	return 0;
}

0.0分

1 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

编程语言转换

万能编程问答

代码解释器

　　评论区

后来呢

你这个输入怎么终止，我一直输入，没有尽头的。我用了Ctrl+z，也没有停止输入的循环

2020-05-02 00:10:54

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

肺炎大作战-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

Cylinder （C语言描述，蓝桥杯）

JAM计数法（C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【偶数求和】（C++代码）

发工资咯（C语言代码）

简单的a+b （C语言代码）

【回文数(二)】（C语言代码）

毛豆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题10.4 （Java代码）

C语言程序设计教程（第三版）课后习题8.7 （C语言代码）

C语言程序设计教程（第三版）课后习题7.5 （C++代码）

C语言程序设计教程（第三版）课后习题9.8 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

肺炎大作战-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.3 （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

Cylinder （C语言描述，蓝桥杯）

JAM计数法 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

【偶数求和】 （C++代码）

发工资咯 （C语言代码）

简单的a+b （C语言代码）

【回文数(二)】 （C语言代码）

　　评论区

JAM计数法（C语言代码）

【偶数求和】（C++代码）

发工资咯（C语言代码）

【回文数(二)】（C语言代码）