正文

分析

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

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

多余是什么意思呢？
设若

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)

，华丽通过。

CPP

#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;
}

题解：AT_abc392_e [abc392E] Cables and Servers

文章操作

正文

分析

思路

代码

相关推荐

评论

题解：AT_abc392_e [abc392E] Cables and Servers