题解：AT_abc392_e [abc392E] Cables and Servers

fede · 2025-02-09 19:23:11 · 题解

正文

分析

最开始，一定有许多互不相连集合（这里将最开始联通的块成为集合），为了让这些互不相连的集合连成一块，我们需要拆掉一些原有的线。

为了保证图是联通的，我们只需要留下不多余的线。

多余是什么意思呢？
设若 A,B 两点已经联通了，此时又加进来一条连接 A,B 的边，那么这条边就是多余的，它即使不存在也不会改变原来的联通情况。

我们可以让这些多余的边发挥作用，将它们连接到不同的集合。

另外，易得最开始的集合个数即为操作次数。

思路

两点是否联通可以用并查集实现。

找出多余的线，把这些线放到一个工作集合当中。

遍历工作集合当中的这些多余的线，找到可以发挥作用的线，将其连到不同的集合。

怎么连到不同的集合？
我们可以先将不同的集合处理出来，将它们的根储存在 S 数组中，再使用双指针类似尺取法的方式，就可以找到不同的集合。具体方法是这样的：

• 设现在总共有 k 个集合，那么 l=1,r=k。
• 像 \text{Kruskal} 算法，从工作集合中不断选边。
• 若当前这条边的端点 x 与 S_r 不是同个集合，那么两个集合合并，S_r 这个独立的集合就不存在了，留下了 x 所在的集合，r 即减少 1。再选下一条边……
• 否则，若当前这条边的端点 x 与 S_l 不是同个集合，那么两个集合合并，S_l 这个独立的集合就不存在了，留下了 x 所在的集合，l 即增加 1。再选下一条边……
• 直到 l=r，说明集合已经合并完了。

代码

时间复杂度 O(n)，空间复杂度 O(n)，华丽通过。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
const int N=1e6+10;
struct node{
    int x,y;
};
node a[N];
queue<int> b;
int n,m;
int fa[N];
int ct[N],k;
int find(int x){
    if(x==fa[x]){
        return x;
    }
    return fa[x]=find(fa[x]);
}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        cin>>a[i].x>>a[i].y;
        int fx=find(a[i].x),fy=find(a[i].y);
        if(fx==fy){
            b.push(i);
            continue;
        }
        fa[fx]=fy;
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==i){
            ct[++k]=i;
        }
    }
    cout<<k-1<<endl;
    int l=1,r=k;
    while(!b.empty()&&l!=r){
        int id=b.front();
        b.pop();
        int fx=find(a[id].x);
        cout<<id<<' '<<a[id].y<<' ';
        if(fx==ct[r]){
            cout<<ct[l]<<endl;
            fa[ct[l]]=fx;
            l++;
        }else{
            cout<<ct[r]<<endl;
            fa[ct[r]]=fx;
            r--;
        }
    }
    return 0;
}