同値関係(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

参考