发帖
雷达卡
并查集（Union-Find）在动态连通性问题中的应用解析
并查集，又称不相交集合（Disjoint Set Union），是一种高效管理元素分组关系的数据结构，尤其适用于处理图中节点的连通性问题。其核心操作包含三个部分：初始化、查找与合并。
初始化阶段，每个元素独立成一个集合，自身即为该集合的代表元；查找操作用于确定某个元素所属集合的根节点，常配合路径压缩优化效率；合并则将两个不同集合归并为一，通常依据秩或大小进行优化，以保持树的平衡。
题目背景与建模分析
故事源于《三国演义》中诸葛亮布七星灯续命的情节。若七盏主灯能持续点亮七日，则可延寿成功。然而第七日魏延闯入，其披风意外吹灭一盏主灯，导致仪式失败。后文揭示魏延确有反心，印证了天意难违。
假设你穿越至此，为保仪式成功，提前在军帐内布置若干迷惑性灯具。已知1至7号为主灯，构成“七星灯”主体，其余灯可能通过直接或间接连接依附于该体系。一旦任意一盏主灯被熄灭，借命即告失败。现共有 n 盏灯和 m 条连接关系（表示两灯相连，翻倒一盏会引发连锁倾覆）。目标是：在确保主灯群完整无损的前提下，计算魏延最多能安全打翻多少盏非关键灯，并统计整体形成的灯群数量。
所谓“灯群”，是指通过直接或间接连接形成的一个连通块。同一灯群内的任一灯被掀倒，整个群体都将受影响。
输入输出说明
输入格式：
第一行给出两个整数 n 和 m（满足 7 ≤ n ≤ 200000，6 ≤ m ≤ 500000），分别代表灯的总数与连接关系的数量。
接下来 m 行，每行包含两个整数，表示编号对应的两盏灯之间存在连接。
输出格式：
输出两个整数：第一个为在不影响七星灯存活的情况下，最多可被熄灭的灯数；第二个为总共存在的灯群个数。
10 8
1 2
1 3
1 4
1 5
1 6
8 9
9 10
8 10样例演示
输入示例：
10 9 1 2 2 3 3 4 4 5 5 6 6 1 7 1 8 9 9 10
输出示例：
3 2解题思路详解
观察可知，1~7号灯必须全部属于同一个连通块——这是七星灯生效的前提。尽管输入中未显式列出所有连接（如7与1之间的边），但根据题意应默认它们彼此连通或可通过已有路径到达。
利用并查集对所有连接关系进行处理，最终将所有灯划分为若干互不相交的集合（即灯群）。特别地，只要1~7号灯处于同一集合，则该集合被视为“主灯群”，不可有任何破坏。
其余每一个独立的灯群（不含1~7中任何一盏）均可被完全清除，因为它们不影响主灯运行。因此，答案的第一部分等于所有非主灯群中灯的数量总和。
第二部分答案即为并查集中根节点的总数，也就是连通块的个数。
以样例为例：1~7号灯通过多条边连接成一个整体，形成主灯群；而8、9、10三盏灯虽无关联于主群，但彼此连接构成另一个连通块。因此共存在2个灯群，其中仅有一个为主灯群，另一个可全数移除，故最多可掀灭3盏灯。
C++ 实现要点
初始化结构：
定义父节点数组 parent[] 与秩数组 rank[]，初始时每个节点的父节点指向自己，秩设为0。
void init(int x){//初始化
for(int i = 1; i <= x ;i++){
parent[i] = i;//初始化每个灯为一个独立的个体
visited[i] = false;
star[i] = false;
len[i] = 1;//还原每个灯群
}
}查找函数（带路径压缩）：
递归查找根节点，并在回溯过程中将沿途节点直接挂载至根下，提升后续查询效率。
int findx(int x){//查找
if (parent[x] != x){
parent[x] = findx(parent[x]);//找到该灯属于哪个灯群,路径压缩
}
return parent[x];
}合并操作（按秩合并）：
比较两棵树的深度，将较浅者合并到较深者之下，避免树过高，维持近似常数级操作复杂度。
void merge(int x,int y){//合并
int fx = findx(x);
int fy = findx(y);
if (fx == fy) return;
if (len[fx] < len[fy]){
swap(fx, fy);//统一合并到数字大的主体中
}
parent[fy] = fx;
len[fx] += len[fy]; //更新灯群中的具体灯数
}完整代码实现：
整合上述模块，读入数据后依次执行合并操作，最后遍历统计各连通块大小及归属情况，排除包含主灯的集合，累加其余集合的灯数即可得出结果。
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int parent[MAXN];
int len[MAXN];
bool visited[MAXN];
bool star[MAXN];
void init(int x){//初始化
for(int i = 1; i <= x ;i++){
parent[i] = i;//初始化每个灯为一个独立的个体
visited[i] = false;
star[i] = false;
len[i] = 1;//还原每个灯群
}
}
int findx(int x){//查找
if (parent[x] != x){
parent[x] = findx(parent[x]);//找到该灯属于哪个灯群,路径压缩
}
return parent[x];
}
void merge(int x,int y){//合并
int fx = findx(x);
int fy = findx(y);
if (fx == fy) return;
if (len[fx] < len[fy]){
swap(fx, fy);//统一合并到数字大的主体中
}
parent[fy] = fx;
len[fx] += len[fy]; //更新灯群中的具体灯数
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
while(cin>>n>>m){
init(n);
for (int i = 2 ; i <= 7 ;i++){//合并1-7号为主体
merge(1,i);
}
for (int i = 0 ; i < m ; i++){
int u,v;
cin>>u>>v;
merge(u,v);
}
for (int i = 1 ; i <= 7 ;i++){
int root = findx(i);
star[root] = true;
}
long long group_cnt = 0;
long long ans_cnt = 0;
for (int i = 1 ;i <= n ;i++){
int root = findx(i);
if (visited[root]){
continue;
}
visited[root] = true;
group_cnt++;
if (!star[root]){
ans_cnt += len[root];//与七星灯主体无关联的
}
}
cout<<ans_cnt<<" "<<group_cnt<<endl;
}
return 0;
}
京公网安备 11010802022788号
