![题解：洛谷 P14552 [ROI 2013 Day1] 乌拉尔冰球赛](http://pic.xiahunao.cn/yaotu/题解：洛谷 P14552 [ROI 2013 Day1] 乌拉尔冰球赛)
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14552 [ROI 2013 Day1] 乌拉尔冰球赛 - 洛谷【题目描述】为了普及冰球运动并提高乌拉尔地区冰球队的技术水平组织了一场全乌拉尔锦标赛。锦标赛邀请了来自乌拉尔各城市的N NN支冰球队参加。在前两轮比赛后每支球队各进行了一场比赛结果发现参赛队伍过多。锦标赛组织者决定只允许K KK支球队继续参赛且这些球队中任意两支在前两轮比赛中均未相遇。需要编写一个程序找出满足条件的K KK支球队集合或者输出无法实现的消息。如果存在多个符合条件的集合只需找出其中任意一个。【输入】输入文件的第一行包含一个数字N NN2 ⩽ N ⩽ 100 , 000 2 \leqslant N \leqslant 100,0002⩽N⩽100,000N NN为偶数。随后的N NN行包含所有已进行比赛的描述。每场比赛的描述由两个不超过N NN的自然数组成——表示参加比赛的球队编号。前N / 2 N/2N/2行对应第一轮的比赛其余行对应第二轮的比赛。输入文件的最后一行包含一个数字K KK2 ⩽ K ⩽ N 2 \leqslant K \leqslant N2⩽K⩽N。保证每支球队恰好进行了两场比赛一场在第一轮一场在第二轮。【输出】输出文件应包含如果无解则仅输出一个数字0 00否则输出K KK个不同的数字——所选球队的编号。【输入样例】6 1 2 3 5 4 6 2 3 4 5 1 6 3【输出样例】1 4 3【核心思想】问题分析给定N NN支球队的比赛记录每支球队进行两场比赛需要选出K KK支球队使得这K KK支球队中任意两支都没有比赛过。将比赛关系建模为图球队为节点比赛为边。问题转化为在图中选出K KK个互不相邻的节点独立集。由于每支球队恰好参加两场比赛图由若干个环组成是二分图。算法选择二分图染色使用 DFS 对图进行黑白染色将节点分为两个集合贪心选择选择较大的独立集颜色数量较多的集合从中取K KK个节点关键步骤读入N NN支球队构建无向图邻接表G GG读入目标数量K KK对每个未染色的连通块进行 DFS 染色将起始节点染成红色c o l o r 1 color 1color1递归地将邻居染成相反颜色黑色c o l o r − 1 color -1color−1若发现邻居已染相同颜色则不是二分图本题保证是二分图统计所有红色节点存入a n s ansans数组若∣ a n s ∣ ≥ K |ans| \geq K∣ans∣≥K输出前K KK个红色节点否则输出0 00时间/空间复杂度时间复杂度O ( N ) O(N)O(N)每个节点和边只被访问一次总边数为N NN因为每支球队两场比赛空间复杂度O ( N ) O(N)O(N)存储邻接表和颜色数组二分图独立集的核心思想二分图性质节点可分为两个集合集合内部无边所有边都连接两个集合独立集同一颜色集合内的节点互不相邻构成独立集最大独立集选择两个颜色集合中较大的一个即为最大独立集本题变体只需找到大小至少为K KK的独立集选择红色集合即可适用于匹配问题、资源分配、冲突避免等场景【算法标签】#普及 #二分图【代码详解】#includebits/stdc.h// 包含所有标准库头文件usingnamespacestd;// 使用标准命名空间constintN100010;// 定义最大节点数intn,k;// 节点数n所需红色节点数kvectorintG[N],ans;// 邻接表G存储图ans存储所有红色节点intcolor[N];// 颜色数组0表示未染色1表示红色-1表示黑色boolflag;// 是否为二分图的标志voiddfs(intx)// 深度优先搜索函数{if(color[x]1)// 如果当前节点是红色ans.push_back(x);// 将红色节点加入答案数组for(inti0;iG[x].size();i)// 遍历当前节点的所有邻居{intyG[x][i];// 获取邻居节点if(color[x]color[y])// 如果当前节点和邻居颜色相同{flagfalse;// 不是二分图return;// 返回}if(color[y]0)// 如果邻居节点未染色{color[y]-color[x];// 将邻居染成相反颜色dfs(y);// 递归处理邻居节点}}}intmain()// 主函数{cinn;// 输入节点数for(inti1;in;i)// 构建图的邻接表{intu,v;// 边的两个端点cinuv;// 输入边的信息G[v].push_back(u);// 添加无向边G[u].push_back(v);}cink;// 输入需要输出的红色节点数量for(inti1;in;i)// 遍历所有节点{if(color[i]0)// 如果节点未染色{color[i]1;// 染成红色dfs(i);// 从该节点开始深度优先搜索}}if(ans.size()k)// 如果红色节点数量满足要求{for(inti0;ik;i)// 输出前k个红色节点coutans[i] ;// 输出红色节点coutendl;// 换行}else// 如果红色节点数量不足{cout0endl;// 输出0}return0;// 程序正常结束}【运行结果】6 1 2 3 5 4 6 2 3 4 5 1 6 3 1 3 4
题解：洛谷 P14552 [ROI 2013 Day1] 乌拉尔冰球赛
发布时间：2026/6/14 13:30:32
本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。欢迎大家订阅我的专栏算法题解C与Python实现附上汇总贴算法竞赛备考冲刺必刷题C | 汇总【题目来源】洛谷P14552 [ROI 2013 Day1] 乌拉尔冰球赛 - 洛谷【题目描述】为了普及冰球运动并提高乌拉尔地区冰球队的技术水平组织了一场全乌拉尔锦标赛。锦标赛邀请了来自乌拉尔各城市的N NN支冰球队参加。在前两轮比赛后每支球队各进行了一场比赛结果发现参赛队伍过多。锦标赛组织者决定只允许K KK支球队继续参赛且这些球队中任意两支在前两轮比赛中均未相遇。需要编写一个程序找出满足条件的K KK支球队集合或者输出无法实现的消息。如果存在多个符合条件的集合只需找出其中任意一个。【输入】输入文件的第一行包含一个数字N NN2 ⩽ N ⩽ 100 , 000 2 \leqslant N \leqslant 100,0002⩽N⩽100,000N NN为偶数。随后的N NN行包含所有已进行比赛的描述。每场比赛的描述由两个不超过N NN的自然数组成——表示参加比赛的球队编号。前N / 2 N/2N/2行对应第一轮的比赛其余行对应第二轮的比赛。输入文件的最后一行包含一个数字K KK2 ⩽ K ⩽ N 2 \leqslant K \leqslant N2⩽K⩽N。保证每支球队恰好进行了两场比赛一场在第一轮一场在第二轮。【输出】输出文件应包含如果无解则仅输出一个数字0 00否则输出K KK个不同的数字——所选球队的编号。【输入样例】6 1 2 3 5 4 6 2 3 4 5 1 6 3【输出样例】1 4 3【核心思想】问题分析给定N NN支球队的比赛记录每支球队进行两场比赛需要选出K KK支球队使得这K KK支球队中任意两支都没有比赛过。将比赛关系建模为图球队为节点比赛为边。问题转化为在图中选出K KK个互不相邻的节点独立集。由于每支球队恰好参加两场比赛图由若干个环组成是二分图。算法选择二分图染色使用 DFS 对图进行黑白染色将节点分为两个集合贪心选择选择较大的独立集颜色数量较多的集合从中取K KK个节点关键步骤读入N NN支球队构建无向图邻接表G GG读入目标数量K KK对每个未染色的连通块进行 DFS 染色将起始节点染成红色c o l o r 1 color 1color1递归地将邻居染成相反颜色黑色c o l o r − 1 color -1color−1若发现邻居已染相同颜色则不是二分图本题保证是二分图统计所有红色节点存入a n s ansans数组若∣ a n s ∣ ≥ K |ans| \geq K∣ans∣≥K输出前K KK个红色节点否则输出0 00时间/空间复杂度时间复杂度O ( N ) O(N)O(N)每个节点和边只被访问一次总边数为N NN因为每支球队两场比赛空间复杂度O ( N ) O(N)O(N)存储邻接表和颜色数组二分图独立集的核心思想二分图性质节点可分为两个集合集合内部无边所有边都连接两个集合独立集同一颜色集合内的节点互不相邻构成独立集最大独立集选择两个颜色集合中较大的一个即为最大独立集本题变体只需找到大小至少为K KK的独立集选择红色集合即可适用于匹配问题、资源分配、冲突避免等场景【算法标签】#普及 #二分图【代码详解】#includebits/stdc.h// 包含所有标准库头文件usingnamespacestd;// 使用标准命名空间constintN100010;// 定义最大节点数intn,k;// 节点数n所需红色节点数kvectorintG[N],ans;// 邻接表G存储图ans存储所有红色节点intcolor[N];// 颜色数组0表示未染色1表示红色-1表示黑色boolflag;// 是否为二分图的标志voiddfs(intx)// 深度优先搜索函数{if(color[x]1)// 如果当前节点是红色ans.push_back(x);// 将红色节点加入答案数组for(inti0;iG[x].size();i)// 遍历当前节点的所有邻居{intyG[x][i];// 获取邻居节点if(color[x]color[y])// 如果当前节点和邻居颜色相同{flagfalse;// 不是二分图return;// 返回}if(color[y]0)// 如果邻居节点未染色{color[y]-color[x];// 将邻居染成相反颜色dfs(y);// 递归处理邻居节点}}}intmain()// 主函数{cinn;// 输入节点数for(inti1;in;i)// 构建图的邻接表{intu,v;// 边的两个端点cinuv;// 输入边的信息G[v].push_back(u);// 添加无向边G[u].push_back(v);}cink;// 输入需要输出的红色节点数量for(inti1;in;i)// 遍历所有节点{if(color[i]0)// 如果节点未染色{color[i]1;// 染成红色dfs(i);// 从该节点开始深度优先搜索}}if(ans.size()k)// 如果红色节点数量满足要求{for(inti0;ik;i)// 输出前k个红色节点coutans[i] ;// 输出红色节点coutendl;// 换行}else// 如果红色节点数量不足{cout0endl;// 输出0}return0;// 程序正常结束}【运行结果】6 1 2 3 5 4 6 2 3 4 5 1 6 3 1 3 4
