Submission #62556783

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;
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(obj) begin(obj), end(obj)
typedef long long ll;
typedef pair<int,int> pii;
struct UnionFind {
    vector<int> par, rank, siz;
    UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
    int root(int x) {
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
    bool unite(int x, int y) {
        int rx = root(x), ry = root(y);
        if(rx==ry)return false;
        if(rank[rx]<rank[ry]) swap(rx,ry);
        par[ry]=rx;
        if(rank[rx]==rank[ry]) rank[rx]++;
        siz[rx]+=siz[ry];
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define ALL(obj) begin(obj), end(obj)
typedef long long ll;
typedef pair<int,int> pii;

struct UnionFind {
    vector<int> par, rank, siz;
    UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
    int root(int x) {
        if(par[x] == -1) return x;
        return par[x] = root(par[x]);
    }
    bool unite(int x, int y) {
        int rx = root(x), ry = root(y);
        if(rx==ry)return false;
        if(rank[rx]<rank[ry]) swap(rx,ry);
        par[ry]=rx;
        if(rank[rx]==rank[ry]) rank[rx]++;
        siz[rx]+=siz[ry];
        return true;
    }
};

struct E {
    int id, a, b;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    int cnt=0;
    cin >> N >> M;
    vector<int> A(M), B(M);
    map<pii,int> mp;
    UnionFind uf(N);
    vector<E> extraEdges;
    REP(i, M) {
        cin >> A[i] >> B[i];
        A[i]--, B[i]--;
        // 自己ループや同じペアの場合は余剰扱い
        if(!mp.count({A[i],B[i]}) && A[i]!=B[i]){
            if(uf.unite(A[i],B[i])) {
                cnt++; // spanning tree に使った
            } else {
                extraEdges.push_back({i, A[i], B[i]});
            }
        } else {
            extraEdges.push_back({i, A[i], B[i]});
        }
        mp[{A[i],B[i]}] = 1;
    }
    
    // 各サーバーの連結成分（代表）は uf.root(i) により得られる
    vector<int> compList;
    REP(i,N) compList.push_back(uf.root(i));
    sort(ALL(compList));
    compList.erase(unique(ALL(compList)), compList.end());
    
    // 成分ごとに，その成分に属する余剰（変更可能）ケーブル候補を、端点情報付きで集める
    vector<vector<E>> extras(N);
    for(auto &e : extraEdges){
        int comp = uf.root(e.a);
        extras[comp].push_back(e);
    }
    
    // 貪欲に操作するため，まず変更可能なケーブル数が多い成分をメインに選ぶ
    int mainComp = compList[0];
    for(auto r : compList){
        if(extras[r].size() > extras[mainComp].size()){
            mainComp = r;
        }
    }
    
    // 操作 (ケーブル番号, 変更前のサーバー, 変更後のサーバー) を記録（内部は0-indexed; 出力時 +1）
    vector<tuple<int,int,int>> ops;
    // 各成分をメイン成分へ統合
    for(auto r : compList){
        if(r == mainComp) continue;
        // まず，余剰ケーブルがある成分側から利用できれば，その成分に記録してある端点（e.a）で再配線
        if(!extras[r].empty()){
            E candidate = extras[r].back();
            extras[r].pop_back();
            ops.push_back({candidate.id, candidate.a, mainComp});
        }
        // なければ，メイン側の余剰ケーブルから，端点を r に変更
        else if(!extras[mainComp].empty()){
            E candidate = extras[mainComp].back();
            extras[mainComp].pop_back();
            ops.push_back({candidate.id, candidate.a, r});
        }
        // マージ後，両成分の余剰候補を統合
        for(auto &e : extras[r])
            extras[mainComp].push_back(e);
    }
    
    cout << ops.size() << "\n";
    // 出力は1-indexedに変換して表示
    for(auto &op : ops){
        int cable, before, after;
        tie(cable, before, after) = op;
        cout << cable+1 << " " << before+1 << " " << after+1 << "\n";
    }
    
    return 0;
}

Submission Info

Judge Result