Submission #62553531

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define N 200005
struct DSU{
    vector<int> fa,si;
    int size;
    DSU(int x=0){
        init(x);
    }
    void init(int n){
        fa.resize(n+1);
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        si.assign(n+1,1);
        size=n;
    }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define N 200005

struct DSU{
    vector<int> fa,si;
    int size;

    DSU(int x=0){
        init(x);
    }

    void init(int n){
        fa.resize(n+1);
        for(int i=1;i<=n;i++){
            fa[i]=i;
        }
        si.assign(n+1,1);
        size=n;
    }

    int find(int x){
        return x==fa[x]?x:fa[x]=find(fa[x]);
    }

    bool merge(int x,int y){
        x=find(x);y=find(y);
        // if(si[x]<si[y])swap(x,y);
        if(x==y)return false;
        fa[y]=x;
        si[x]+=si[y];
        return true;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    int n,m;
    cin>>n>>m;

    DSU dsu(n);
    vector<int> l(m+1),r(m+1);
    vector<int> les;
    for(int i=1;i<=m;i++){
        cin>>l[i]>>r[i];
        if(!dsu.merge(l[i],r[i]))les.push_back(i);
    }
    set<int> bl;
    for(int i=1;i<=n;i++){
        bl.insert(dsu.find(i));
    }
    int pt=0;
    vector<array<int,3>> op;
    while(bl.size()>=2){
        int f=dsu.find(l[les[pt]]);
        if(f==*(bl.begin())){
            int v=*(bl.rbegin());
            op.push_back({les[pt],l[les[pt]],v});
            dsu.merge(f,v);
            bl.erase(v);
            pt++;  
        }else{
            int v=*(bl.begin());
            op.push_back({les[pt],l[les[pt]],v});
            dsu.merge(f,v);
            bl.erase(v);
            pt++;
        }
    }
    cout<<op.size()<<"\n";
    sort(op.begin(),op.end());
    for(auto c:op){
        cout<<c[0]<<" "<<c[1]<<" "<<c[2]<<"\n";
    }
    return 0;
}

Submission Info

Judge Result