結果

問題 No.556 仁義なきサルたち
ユーザー fine
提出日時 2017-08-11 22:43:33
言語 C++14
(gcc 9.2.0)
結果
AC  
実行時間 18 ms
コード長 1,373 Byte
コンパイル時間 1,974 ms
使用メモリ 1,568 KB
最終ジャッジ日時 2019-12-29 00:55:20

テストケース

テストケース表示
入力 結果 実行時間
使用メモリ
test1.txt AC 3 ms
1,520 KB
test2.txt AC 3 ms
1,520 KB
test3.txt AC 3 ms
1,520 KB
test4.txt AC 3 ms
1,520 KB
test5.txt AC 3 ms
1,520 KB
test6.txt AC 4 ms
1,520 KB
test7.txt AC 4 ms
1,516 KB
test8.txt AC 4 ms
1,520 KB
test9.txt AC 4 ms
1,524 KB
test10.txt AC 5 ms
1,524 KB
test11.txt AC 5 ms
1,528 KB
test12.txt AC 5 ms
1,528 KB
test13.txt AC 5 ms
1,524 KB
test14.txt AC 10 ms
1,548 KB
test15.txt AC 10 ms
1,544 KB
test16.txt AC 11 ms
1,544 KB
test17.txt AC 17 ms
1,564 KB
test18.txt AC 18 ms
1,568 KB
test19.txt AC 18 ms
1,568 KB
x_append10.txt AC 18 ms
1,564 KB
x_append11.txt AC 17 ms
1,564 KB
x_append12.txt AC 18 ms
1,564 KB
テストケース一括ダウンロード

ソースコード

diff #
#include <bits/stdc++.h>

using namespace std;

struct Union_Find {
    //各要素が属する集合の代表(根)を管理する
    //もし、要素xが根であればdata[x]は負の値を取り、-data[x]はxが属する集合の大きさに等しい
    vector<int> data;
    
    Union_Find(int size) : data(size, -1) {}
    bool Union(int x, int y) {
        x = Find(x);
        y = Find(y);
        bool is_union = (x != y);
        if (is_union) {
            if (data[x] > data[y] || (data[x] == data[y] && x > y)) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return is_union;
    }
    int Find(int x) {
        if (data[x] < 0) { //要素xが根である
            return x;
        } else {
            data[x] = Find(data[x]); //data[x]がxの属する集合の根でない場合、根になるよう更新される
            return data[x];
        }
    }
    bool same(int x, int y) {
        return Find(x) == Find(y);
    }
    int size(int x) {
        return -data[Find(x)];
    }
};

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n, m;
	cin >> n >> m;
	Union_Find uf(n);
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		uf.Union(a, b);
	}

	for (int i = 0; i < n; i++) {
		int root = uf.Find(i);
		cout << (root < 0 ? i + 1 : root + 1) << endl;
	}
	return 0;
}
0