毛豆

用户名：liuyt

访问量：16842

签　名：

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

　　自我简介：

TA的其他文章

肺炎大作战-题解(C++代码)
浏览：186

你可能喜欢

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

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

　　作者: 毛豆　　　　发表时间：2020-04-30 09:38:19 浏览：186　|　评论：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语言程序设计教程（第三版）课后习题6.8 （Java代码）

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

人见人爱A+B （C++代码）

printf基础练习2 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

评论区

精彩推荐

点我有惊喜！你懂得！

C二级辅导-计负均正（C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

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

字符串比较（C语言代码）答案错误？？？？

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

求组合数（C语言代码）

数对（C语言代码）

母牛的故事（C语言代码）

淘淘的名单（C语言代码）

毛豆

TA的其他文章

你可能喜欢

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

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

人见人爱A+B （C++代码）

printf基础练习2 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

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

评论区

精彩推荐

点我有惊喜！你懂得！

C二级辅导-计负均正 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(3)，复杂度最低的方法没有之一！！！！！

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

字符串比较 （C语言代码）答案错误？？？？

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

求组合数 （C语言代码）

数对 （C语言代码）

母牛的故事 （C语言代码）

淘淘的名单 （C语言代码）

　　评论区

C二级辅导-计负均正（C语言代码）

字符串比较（C语言代码）答案错误？？？？

求组合数（C语言代码）

数对（C语言代码）

母牛的故事（C语言代码）

淘淘的名单（C语言代码）