Submission #62562544

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
class DSU
{
	private:
		int fa[N];
	public:
		void init(int n){for(int i=1;i<=n;i++)fa[i]=i;}
		int find(int x){return (fa[x]==x?x:fa[x]=find(fa[x]));}
		void merge(int x,int y){fa[find(x)]=find(y);}
		bool same(int x,int y){return find(x)==find(y);}
}dsu;
bool flg[N],vis[N];
int u[N],v[N],id[N],num[N];
deque<int>que;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    cin>>n>>m;
    dsu.init(N-1);
    int tot=0;
    for(int i=1;i<=m;i++)
    {
        cin>>u[i]>>v[i];
        if(dsu.same(u[i],v[i]))num[++tot]=i;
        else dsu.merge(u[i],v[i]);
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        id[i]=dsu.find(i);
        if(!flg[id[i]])flg[id[i]]=true,ans++;
    }
    cout<<ans-1<<'\n';
    for(int i=1;i<=n;i++)
        if(!vis[id[i]])vis[id[i]]=true,que.push_back(id[i]);
    for(int i=1;i<ans;i++)
    {
        cout<<num[i]<<' '<<v[num[i]]<<' ';
        while(dsu.find(v[num[i]])==dsu.find(que.front()))que.pop_front();
        cout<<que.front()<<'\n';
        dsu.merge(v[num[i]],que.front());
    }
    return 0;
}

Submission Info

Judge Result