题解：洛谷 P14552 [ROI 2013 Day1] 乌拉尔冰球赛

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

---

【题目来源】

洛谷：P14552 [ROI 2013 Day1] 乌拉尔冰球赛 - 洛谷

【题目描述】

为了普及冰球运动并提高乌拉尔地区冰球队的技术水平，组织了一场全乌拉尔锦标赛。锦标赛邀请了来自乌拉尔各城市的N NN支冰球队参加。

在前两轮比赛后，每支球队各进行了一场比赛，结果发现参赛队伍过多。锦标赛组织者决定只允许K KK支球队继续参赛，且这些球队中任意两支在前两轮比赛中均未相遇。

需要编写一个程序，找出满足条件的K KK支球队集合，或者输出无法实现的消息。如果存在多个符合条件的集合，只需找出其中任意一个。

【输入】

输入文件的第一行包含一个数字N NN（2 ⩽ N ⩽ 100 , 000 2 \leqslant N \leqslant 100,0002⩽N⩽100,000，N NN为偶数）。

随后的N NN行包含所有已进行比赛的描述。每场比赛的描述由两个不超过N NN的自然数组成——表示参加比赛的球队编号。
前N / 2 N/2N/2行对应第一轮的比赛，其余行对应第二轮的比赛。

输入文件的最后一行包含一个数字K KK（2 ⩽ 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

【核心思想】

1. 问题分析：给定N NN支球队的比赛记录（每支球队进行两场比赛），需要选出K KK支球队，使得这K KK支球队中任意两支都没有比赛过。将比赛关系建模为图：球队为节点，比赛为边。问题转化为在图中选出K KK个互不相邻的节点（独立集）。由于每支球队恰好参加两场比赛，图由若干个环组成，是二分图。

2. 算法选择：

   • 二分图染色：使用 DFS 对图进行黑白染色，将节点分为两个集合
   • 贪心选择：选择较大的独立集（颜色数量较多的集合），从中取K KK个节点

3. 关键步骤：

   • 读入N NN支球队，构建无向图邻接表G GG
   • 读入目标数量K KK
   • 对每个未染色的连通块进行 DFS 染色：
     • 将起始节点染成红色（c o l o r = 1 color = 1color=1）
     • 递归地将邻居染成相反颜色（黑色，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

4. 时间/空间复杂度：

   • 时间复杂度：O ( N ) O(N)O(N)，每个节点和边只被访问一次（总边数为N NN，因为每支球队两场比赛）
   • 空间复杂度：O ( N ) O(N)O(N)，存储邻接表和颜色数组

5. 二分图独立集的核心思想：

   • 二分图性质：节点可分为两个集合，集合内部无边，所有边都连接两个集合
   • 独立集：同一颜色集合内的节点互不相邻，构成独立集
   • 最大独立集：选择两个颜色集合中较大的一个，即为最大独立集
   • 本题变体：只需找到大小至少为K KK的独立集，选择红色集合即可
   • 适用于匹配问题、资源分配、冲突避免等场景

【算法标签】

#普及 #二分图

【代码详解】

#include<bits/stdc++.h>// 包含所有标准库头文件usingnamespacestd;// 使用标准命名空间constintN=100010;// 定义最大节点数intn,k;// 节点数n，所需红色节点数kvector<int>G[N],ans;// 邻接表G存储图，ans存储所有红色节点intcolor[N];// 颜色数组，0表示未染色，1表示红色，-1表示黑色boolflag;// 是否为二分图的标志voiddfs(intx)// 深度优先搜索函数{if(color[x]==1)// 如果当前节点是红色ans.push_back(x);// 将红色节点加入答案数组for(inti=0;i<G[x].size();i++)// 遍历当前节点的所有邻居{inty=G[x][i];// 获取邻居节点if(color[x]==color[y])// 如果当前节点和邻居颜色相同{flag=false;// 不是二分图return;// 返回}if(color[y]==0)// 如果邻居节点未染色{color[y]=-color[x];// 将邻居染成相反颜色dfs(y);// 递归处理邻居节点}}}intmain()// 主函数{cin>>n;// 输入节点数for(inti=1;i<=n;i++)// 构建图的邻接表{intu,v;// 边的两个端点cin>>u>>v;// 输入边的信息G[v].push_back(u);// 添加无向边G[u].push_back(v);}cin>>k;// 输入需要输出的红色节点数量for(inti=1;i<=n;i++)// 遍历所有节点{if(color[i]==0)// 如果节点未染色{color[i]=1;// 染成红色dfs(i);// 从该节点开始深度优先搜索}}if(ans.size()>=k)// 如果红色节点数量满足要求{for(inti=0;i<k;i++)// 输出前k个红色节点cout<<ans[i]<<" ";// 输出红色节点cout<<endl;// 换行}else// 如果红色节点数量不足{cout<<0<<endl;// 输出0}return0;// 程序正常结束}

【运行结果】

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