結果

問題 No.556 仁義なきサルたち
ユーザー puni_kyopropuni_kyopro
提出日時 2018-12-02 17:05:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 21 ms / 2,000 ms
コード長 3,513 bytes
コンパイル時間 649 ms
コンパイル使用メモリ 73,736 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-01 05:24:10
合計ジャッジ時間 1,529 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 2 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 3 ms
5,376 KB
testcase_11 AC 4 ms
5,376 KB
testcase_12 AC 4 ms
5,376 KB
testcase_13 AC 8 ms
5,376 KB
testcase_14 AC 10 ms
5,376 KB
testcase_15 AC 10 ms
5,376 KB
testcase_16 AC 17 ms
5,376 KB
testcase_17 AC 18 ms
5,376 KB
testcase_18 AC 21 ms
5,376 KB
testcase_19 AC 20 ms
5,376 KB
testcase_20 AC 21 ms
5,376 KB
testcase_21 AC 21 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<vector>
#include<algorithm>
#include<cctype>
#include<utility>
#include<string>
#include<cstring>
#include<cmath>
#include<numeric>
#include<queue>
#include<climits>
#include<cstdio>


#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
//#define INF ((LLONG_MAX) / (2))
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long int ll;
typedef pair<ll,int> LL_IP;
typedef pair<ll,ll> LL_LLP;
#define INF 1e9+7


typedef struct union_find{
    
    vector<int> pa;//親
    vector<int> ra;//木の深さ
    vector<int> num;//根についている個数
    //n要素で初期化
    void init(int n){
        pa.resize(n);
        ra.resize(n);
        num.resize(n);
        for(int i = 0;i < n;i++){
            pa[i] = i;/*各ノードに番号を振る,この時par[x]=xとなる時は木の根となる*/
            ra[i] = 0;/*各ノード自体の高さは0*/
            num[i] = 1;   
        }
    }
    //木の根を求める
    int find(int x){
        if(pa[x] == x){
            return x;/*根ならそのノードの番号を返す*/
        }else{
            return pa[x] = find(pa[x]);/*根でないならさらにノードの根を探す*/
        }
    }

    //xとyの属する集合を併合する
    void unite(int x,int y){
        x = find(x);//xの根の番号を探す
        y = find(y);//yの根の番号を探す
        if(x == y){//一致すればつながっている
            return;
        }
        if(num[x] < num[y]){//xの高さが低いなら高いほうにつなぐ、そして高さは大きい方(y)になる
            pa[x] = y;
            num[y] += num[x];
        }else{
            pa[y] = x;//yの高さが低いなら高いほうにつなぐ、そして高さは大きいほう(x)になる
            num[x] += num[y];
            if(ra[x] == ra[y]){//高さが一致しているなら併合の高さは1増える
                ra[x]++;
            }
        }
    }

    //xとyが同じ集合に属するか判定
    bool same(int x,int y){
        return find(x) == find(y);//同じ集合なら1、違うなら0が返る
    }
}UF;

UF tree;

int main(){

    int n,m;
    cin >> n >> m;
    tree.init(n);
    int a,b;
    REP(i,m){
        cin >> a >> b;
        a--;
        b--;
        if(tree.pa[a] != tree.pa[b]){
            //ボスが違う場合
            if(tree.num[tree.find(a)] < tree.num[tree.find(b)]){
                //親の個数が大きい方につなぐ
                tree.unite(tree.find(b),tree.find(a));
            }else if(tree.num[tree.find(a)] > tree.num[tree.find(b)]){
                tree.unite(tree.find(a),tree.find(b));
            }else{
                //親の個数が同じ場合
                if(tree.pa[tree.find(a)] < tree.pa[tree.find(b)]){
                    //1位に近いほうにつなぐ
                    tree.unite(tree.find(a),tree.find(b));
                }else{
                    tree.unite(tree.find(b),tree.find(a));
                }
            }
        }
        //ボスが同じなら何もしない
    }

    REP(i,n){
        cout << tree.find(i)+1 << endl;
    }
    



    return 0;
}
0