結果
問題 | No.556 仁義なきサルたち |
ユーザー |
|
提出日時 | 2017-08-11 23:04:07 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 10 ms / 2,000 ms |
コード長 | 973 bytes |
コンパイル時間 | 715 ms |
コンパイル使用メモリ | 115,380 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 21:29:19 |
合計ジャッジ時間 | 1,713 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 22 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto uf = new UnionFind(N); while (M--) { s = readln.split.map!(to!int); auto a = s[0] - 1; auto b = s[1] - 1; uf.unite(a, b); } foreach (i; 0..N) writeln(uf.find(i) + 1); } class UnionFind { int N; int[] table; this(int n) { N = n; table = new int[](N); fill(table, -1); } int find(int x) { return table[x] < 0 ? x : (table[x] = find(table[x])); } void unite(int x, int y) { x = find(x); y = find(y); if (x == y) return; if (table[x] > table[y] || (table[x] == table[y] && y < x)) swap(x, y); table[x] += table[y]; table[y] = x; } }