ハイフンで区切られた語のリストから関連のある語のセットを抽出する

sample.py

 coding: utf-8
def answer(relations):
    """ハイフンで区切られた語のリストから連関グラフを抽出する
    """
    # 語のペアの集合を生成する
    pairs = [set(r.split('-')) for  r in relations]
    # pairs に要素が残っている間はループ
    while pairs:
        # 起点となるペアを取り出す
        pivot = pairs.pop()
        updated = True
        # 更新がなくなるまでループ
        while updated:
            # pairs から必要に応じて要素を除去するので enumerate を使う
            updated = False
            for i, ref in enumerate(pairs):
                # pivot と ref の交差があるなら語の繋がりがある
                if pivot&ref:
                    # pivot を更新して pivot と ref の合併にする
                    pivot |= ref
                    pairs.pop(i)
                    # 更新があったのでただちにやり直す
                    updated = True
                    break
        # 一通り交差したら閉じていると考えて OK
        print pivot

relations = ('Norwegian-Dunhill', 'Marlboro-blue', 'Brit-3',
             'German-coffee', 'beer-white', 'cat-water',
             'horse-2', 'milk-3', '4-Rothmans',
             'dog-Swede', 'Norwegian-1', 'horse-Marlboro',
             'bird-Brit', '4-green', 'Winfield-beer',
             'Dane-blue', '5-dog', 'blue-horse',
             'yellow-cat', 'Winfield-Swede', 'tea-Marlboro')

answer(relations)