結果
問題 | No.330 Eigenvalue Decomposition |
ユーザー |
|
提出日時 | 2017-07-19 17:57:13 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 218 ms / 5,000 ms |
コード長 | 1,005 bytes |
コンパイル時間 | 744 ms |
コンパイル使用メモリ | 102,360 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-12 21:02:03 |
合計ジャッジ時間 | 4,585 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 31 |
ソースコード
import std.algorithm, std.conv, std.range, std.stdio, std.string;void main(){auto rd = readln.split.to!(size_t[]), n = rd[0], m = rd[1];auto uf = UnionFind!size_t(n);foreach (_; 0..m) {auto rd2 = readln.split[0..2].to!(size_t[]), i = rd2[0]-1, j = rd2[1]-1;uf.unite(i, j);}auto b = new bool[](n);foreach (i; 0..n) b[uf.find(i)] = true;writeln(b.count!"a");}struct UnionFind(T){import std.algorithm, std.range;T[] p; // parentconst T s; // sentinelconst T n;this(T n){this.n = n;p = new T[](n);s = n + 1;p[] = s;}T find(T i){if (p[i] == s) {return i;} else {p[i] = find(p[i]);return p[i];}}void unite(T i, T j){auto pi = find(i), pj = find(j);if (pi != pj) p[pj] = pi;}bool isSame(T i, T j) { return find(i) == find(j); }auto groups(){auto g = new T[][](n);foreach (i; 0..n) g[find(i)] ~= i;return g.filter!(l => !l.empty);}}