实用工具小学数学练习字帖生成在线画板函数绘制拼音字母表在线词典黄历查询中国历史 Excel函数模拟请求 json格式化

栏目分类:

子分类:

名师互学网

名师互学网用户登录

快速导航

当前搜索

当前分类

前沿技术软件开发系统运维产品运营生活办公面试经验考试题库

实用工具

学习工具小学数学练习字帖生成在线画板函数绘制拼音字母表在线词典黄历查询亲戚关系计算安全期计算中国历史 Excel函数模拟请求 json格式化浏览器指纹

名师互学网 > IT > 软件开发 > 后端开发 > C/C++/C#

atcoder regular 111 B

C/C++/C# 更新时间：2026-04-01 22:17:12 发布时间：1633天前 IT归档最新发布模块sitemap 名妆网法律咨询聚返吧英语巴士网伯小乐网商动力

题目

可以把这题，每张牌的两个颜色看作图的两个端点（一个颜色一个端点），然后每次取一种颜色，其实就是每条边只能取一个结点，问最后最多能取几个结点。我们可以发现，只要图的连通块，存在一个环，那么这个连通块所有结点都能选上。树的话就只能取n-1个，因为每条边只能选一个结点吗。所以只需要找出所有连通块，对边数和结点数取min就可以了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#define int long long
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define _BYTE unsigned char
#define HIBYTE(x) (*((_BYTE*)&(x)+1))
#define eps 1e-8
//#define double long double
using namespace std;
int fa[400000+5],n,a,b,ans,sum[400000+5],edge[400000+5];
int fin(int x)
{
	if(fa[x]==x)return x;
	return fa[x]=fin(fa[x]);	
}
signed main()
{
	IO;
	cin>>n;
	for(int i=1;i<=400000+3;i++)
	{
		fa[i]=i;
		sum[i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a>>b;
		int x=fin(a),y=fin(b);
		if(x==y)
		{
			edge[x]++;
		}
		else
		{
			fa[x]=y;
			sum[y]+=sum[x];
			sum[x]=0;
			edge[y]+=edge[x]+1;
			edge[x]=0;
		}
	}
	for(int i=1;i<=400000+3;i++)
	{
		if(fa[i]==i)
		{
			ans+=min(edge[i],sum[i]);
		}
	}
	cout<

转载请注明：文章转载自 www.mshxw.com

本文地址：https://www.mshxw.com/it/311611.html

上一篇 7-139 手机话费

下一篇数据结构3-栈和队列的操作

C/C++/C#相关栏目本月热门文章

热门相关搜索

路由器设置木托盘宝塔面板儿童python教程心情低落朋友圈 vim 双一流学科专升本我的学校日记学校西点培训学校汽修学校情书化妆学校塔沟武校异形模板西南大学排名最精辟人生短句 6步教你追回被骗的钱南昌大学排名清朝十二帝北京印刷学院排名北方工业大学排名北京航空航天大学排名首都经济贸易大学排名中国传媒大学排名首都师范大学排名中国地质大学(北京)排名北京信息科技大学排名中央民族大学排名北京舞蹈学院排名北京电影学院排名中国戏曲学院排名河北政法职业学院排名河北经贸大学排名天津中德应用技术大学排名天津医学高等专科学校排名天津美术学院排名天津音乐学院排名天津工业大学排名北京工业大学耿丹学院排名北京警察学院排名天津科技大学排名北京邮电大学(宏福校区)排名北京网络职业学院排名北京大学医学部排名河北科技大学排名河北地质大学排名河北体育学院排名

关于我们文章归档网站地图联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号：晋ICP备2021003244-6号