Submission #62552796

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 <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <tuple>
using namespace std;
#define REP(i,n) for (int i=0;i<n;i++)
#define ALL(x) (x).begin(), (x).end()
using pii = pair<int,int>;
struct E {
    int id, a, b; // a,b は 0-indexed
};
struct UnionFind {
    vector<int> par, rank, siz;
    UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
    int root(int x) { return par[x] < 0 ? x : par[x] = root(par[x]); }
    bool unite(int x, int y) {
        int rx=root(x), ry=root(y);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <tuple>
using namespace std;
#define REP(i,n) for (int i=0;i<n;i++)
#define ALL(x) (x).begin(), (x).end()

using pii = pair<int,int>;

struct E {
    int id, a, b; // a,b は 0-indexed
};

struct UnionFind {
    vector<int> par, rank, siz;
    UnionFind(int n) : par(n,-1), rank(n,0), siz(n,1) { }
    int root(int x) { return par[x] < 0 ? x : 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;
    }
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M, cnt=0;
    cin >> N >> M;
    vector<int> A(M), B(M);
    map<pii,int> mp;
    UnionFind uf(N);
    vector<E> edge; // spanning forest に使われなかったケーブル（冗長ケーブル）
    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++;
            else edge.push_back({i, A[i], B[i]});
        } else {
            edge.push_back({i, A[i], B[i]});
        }
        mp[{A[i],B[i]}]=1;
    }
    
    // 各サーバーの連結成分代表
    vector<int> R;
    REP(i,N) R.push_back(uf.root(i));
    sort(ALL(R));
    R.erase(unique(ALL(R)), R.end());
    int compCount = R.size();
    if(compCount==1){ 
        cout << 0 << "\n";
        return 0;
    }
    
    // 各成分毎に冗長ケーブルをまとめる
    map<int, vector<E>> compRed;
    for(auto &e : edge){
        int r = uf.root(e.a);
        compRed[r].push_back(e);
    }
    
    // 各成分の冗長ケーブル数を数え、メイン成分としてケーブルを最も持つ成分を選ぶ
    int mainRep = R[0];
    int maxCount = compRed[mainRep].size();
    for(auto r : R){
        if((int)compRed[r].size() > maxCount){
            maxCount = compRed[r].size();
            mainRep = r;
        }
    }
    
    // 各成分と mainRep を接続する操作 (操作回数は compCount - 1)
    vector<tuple<int,int,int>> ops; // (ケーブル番号, 変更前, 変更後) (0-indexed, 後で+1して出力)
    for(auto r : R){
        if(r==mainRep) continue;
        // まず対象成分 r 側の冗長ケーブルがあるなら利用
        if(!compRed[r].empty()){
            E e = compRed[r].back();
            compRed[r].pop_back();
            // e は r 内のケーブル (e.a と e.b は r)
            // 変更前のサーバーは r, 変更後は mainRep, 結果として (mainRep, r) となる
            ops.push_back({e.id, r, mainRep});
        }
        // なければ mainRep 側の冗長ケーブルを使う
        else if(!compRed[mainRep].empty()){
            E e = compRed[mainRep].back();
            compRed[mainRep].pop_back();
            // e は mainRep 内のケーブル (e.a と e.b は mainRep)
            // 変更前のサーバーは mainRep, 変更後は r, 結果として (mainRep, r) となる
            ops.push_back({e.id, mainRep, r});
        }
        // どちらにも無い場合は，本来は存在しない（問題設定より解は必ず存在する）
    }
    
    cout << ops.size() << "\n";
    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