Cables and Servers

F - Cables and Servers

问题陈述

有 NN 台服务器，编号从 11 到 NN，以及 MM 根电缆，编号从 11 到 MM。
电缆 ii 双向连接服务器 AiAi​ 和 BiBi​。

通过执行以下操作若干次（可能为零次），使所有服务器通过电缆连接。

• 操作：选择一根电缆，并将其一端重新连接到另一台服务器。

找出所需的最小操作次数，并输出实现此最小值的操作序列。

约束条件

• 2≤N≤2×1052≤N≤2×105
• N−1≤M≤2×105N−1≤M≤2×105
• 1≤Ai,Bi≤N1≤Ai​,Bi​≤N
• 所有输入值均为整数。

输入

输入通过标准输入以以下格式给出：

NN MM
A1A1​ B1B1​
A2A2​ B2B2​
⋮⋮
AMAM​ BMBM​

输出

设最小操作次数为 KK。打印 K+1K+1 行。

• 第一行应包含 KK。
• 第 (i+1)(i+1) 行应包含三个用空格分隔的整数：在第 ii 次操作中选择的电缆编号、原本连接在该端的服务器编号，以及操作后连接的服务器编号，按此顺序。

如果有多个有效解答，接受其中任何一个。

示例 1

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

1
1 1 3

通过将连接到服务器 11 的电缆 11 的一端重新连接到服务器 33，可以使服务器通过电缆连接。

例如，将连接到服务器 44 的电缆 55 的一端重新连接到服务器 11，或者将连接到服务器 22 的电缆 22 的一端重新连接到服务器 33，也会使所有服务器连接，并被视为正确。

示例 2

4 3
3 4
4 1
1 2

0

可能不需要任何操作。

示例 3

5 4
3 3
3 3
3 3
3 3

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

思路：

Q1：这题是要让所有电脑连通在一起的最小操作序列，我们能否将问题拆分开来

A1：可以将问题分解为 如何将一整个图变成连通图 和 怎样才能有最小的操作序列

Q2：如何将一整个图变成连通图

A2：题目中已经说了，改变一条边的端点，从而使整张图连通，我们想到了并查集

Q3：我们要去改变哪些边的端点呢？

A3：如果说，某两个点，在去掉这条边后，仍然在一张连通图中（即成环的边），就说明这条边可以用，改变后不影响结果

Q4：我们这样是否是有最小的操作序列呢

A4：我们每次只对两个没有连通的分量，链接只一次，一定是最小的操作序列

 代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int n, k, a[200010],b[200010], c[200010],d[200010];
//a用于并查集数组，b第 i 次操作中选择的电缆编号
//c以及操作后连接的服务器编号,d原本连接在该端的服务器编号
int x, y;
int cha(int i) {
	if (a[i] != i) {
		return a[i] = cha(a[i]);
	}
	else {
		return a[i];
	}
}
int main() {
	scanf("%d %d", &n, &k);
	for (int i = 1;i <= n;i++) {
		a[i] = i;
	}//给a赋值
	int j = 0;
	for (int i = 1;i <= k;i++) {
		scanf("%d %d", &x, &y);
		if (cha(x) == cha(y)) {
			d[j] = y;
			b[j++] = i;
		}//将“无用”的线记录下来
		a[cha(x)] = cha(y);//并集
	}
	int sum = 0;
	for (int i = 1;i <=n;i++) {
		if (a[cha(i)] == i) {
			c[sum++] = i;
		}
	}//搜索有几个没有相接的服务器
	sum -= 1;
	printf("%d\n", sum);
	for (int i = 0;i < sum;i++) {
		if (cha(d[i]) == cha(c[i])) {
			int dd = c[i];
			c[i] = c[sum];
			c[sum] = dd;
		}//每条边都有头点，n-1条边将n-1个点于头点相连，最终只有一个点（在头点中）没链接；
         //因此可以放在最后
		printf("%d %d %d\n", b[i],d[i],c[i]);
		a[c[i]] = cha(d[i]);//将连接的并集，防止重复链接
	}
	return 0;
}