from collections import namedtuple

Node = namedtuple('Node', ['id', 'pid'])


ACYCLIC_DATASET = [
    Node(id='a', pid=None),
    Node(id='b1', pid='a'),
    Node(id='c1', pid='b1'),
    Node(id='c2', pid='b1'),
    Node(id='c3', pid='b1'),
    Node(id='b2', pid='a'),
    Node(id='c4', pid='b2'),
    Node(id='c5', pid='b2'),
    Node(id='d1', pid='c5'),
    Node(id='d2', pid='c5'),
]


CYCLIC_DATASET = [
    Node(id='xa2', pid='a'),
    Node(id='xa1', pid='a'),
    Node(id='a', pid='b'),
    Node(id='xb1', pid='b'),
    Node(id='b', pid='c'),
    Node(id='xc1', pid='c'),
    Node(id='c', pid='d'),
    Node(id='xd1', pid='d'),
    Node(id='xd2', pid='d'),
    Node(id='d', pid='e'),
    Node(id='xe1', pid='e'),
    Node(id='e', pid='a'),
]


def find_cycle(items):
    parents = set(i.pid for i in items if i.pid)

    cycle = set()
    for parent in parents.copy():
        item = filter(lambda i: i.id == parent, items)[0]
        print 'item:', item
        if item.pid in parents:
            cycle.add(parent)
            print 'pid:', parent, '->', cycle
        else:
            parents -= set([item.id])
            parents -= cycle
            parents -= set(i.id for i in filter(lambda i: i.pid == item.id, items))
            cycle = set()
            print 'clr:', parents

            if not parents:
                return parents

    return parents


if __name__ == '__main__':
    print find_cycle(CYCLIC_DATASET)