同値関係(Union Find)
結城浩の『Perlクイズ』 [まぐまぐ!] の No.0087 同値関係を求めるクイズをやってみました。
// unionfind.cs using System; using System.Collections.Generic; using System.Linq; // 結城浩の『Perlクイズ』2004-06-18 No.0087 // http://archive.mag2.com/0000015670/20050818225335000.html // // 同値関係を求めるクイズ public class UnionFind { private int[] _par; private int[] _rank; public UnionFind(int size) { _par = new int[size+1]; _rank = new int[size+1]; for (int i = 0; i < _par.Length; i++) { _par[i] = i; } } public int Root(int x) { if (_par[x] == x) return x; else { _par[x] = Root(_par[x]); return _par[x]; } } public bool IsSame(int x, int y) { return Root(x) == Root(y); } public void Unite(int x, int y) { x = Root(x); y = Root(y); if (x == y) return; if (_rank[x] < _rank[y]) { _par[x] = y; } else { _par[y] = x; if (_rank[x] == _rank[y]) { _rank[x]++; } } } } class Program { static void Main() { // A=B のペアを格納 var pairs = new List<Tuple<string, string>>(); // 名前からインデックスへの変換 var dict = new Dictionary<string, int>(); string s; while ((s = Console.ReadLine()) != null) { string[] ab = s.Split('='); pairs.Add(Tuple.Create(ab[0], ab[1])); if (!dict.ContainsKey(ab[0])) { dict[ab[0]] = dict.Count; } if (!dict.ContainsKey(ab[1])) { dict[ab[1]] = dict.Count; } } var u = new UnionFind(dict.Count); foreach (var t in pairs) { // t.Item1 と t.Item2 は同値関係 u.Unite(dict[t.Item1], dict[t.Item2]); } var g = dict.GroupBy(e => u.Root(e.Value), e => e.Key); foreach (var t in g) { Console.WriteLine(string.Join(" ", t.OrderBy(e => e))); } } }
実行結果です。
$ cat in2.txt Alice=Alice Robert=Bob Liz=Beth Lisa=Liza Bess=Beth Elizabeth=Lisa Eliza=Liza Bess=Elizabeth $ mcs unionfind.cs -out:a.exe $ mono a.exe < in2.txt Alice Bob Robert Bess Beth Eliza Elizabeth Lisa Liz Liza
参考
- Algorithms with Python / Union-Find
- http://atc001.contest.atcoder.jp/ 問題 B. Union Find