正文
分析
最开始，一定有许多互不相连集合（这里将最开始联通的块成为集合），为了让这些互不相连的集合连成一块，我们需要拆掉一些原有的线。
为了保证图是联通的，我们只需要留下不多余的线。
多余是什么意思呢？
设若 \(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;
}