Code Jam 2016 Round 1A Q3 BFFs (10% Incorrect solution)

gistfile1.txt

#!/usr/bin/env python3

"""
Failed in this case, does not know why.
1
6
2 3 2 5 4 3
"""

FORMAT = "Case #{}: {}"
DEBUG = False
def debug(*args):
    if DEBUG:
        print(*args)


def DFS(G, v, seen=None, path=None):
    if seen is None:
        seen = []
    if path is None:
        path = [v]

    seen.append(v)

    paths = []
    for t in G[v]:
        if t not in seen:
            t_path = path + [t]
            paths.append(tuple(t_path))
            paths.extend(DFS(G, t, seen, t_path))
    return paths

def generate_chains(bffs, r_bffs):
    for kid_id in bffs:
        chain = [kid_id]
        need_dfs = False
        while True:
            stop = False
            next_bff = bffs[chain[-1]]
            if len(chain) >= 2 and next_bff == chain[-2]:
                need_dfs = True
                break
            elif next_bff in chain:
                break
            chain.append(next_bff)
        if bffs[chain[-1]] != chain[0] and chain[-1] not in r_bffs[chain[-2]]:
            debug(r_bffs)
            debug("Not a circuit: ", chain)
            continue
        debug("orig chain", chain, need_dfs)
        if need_dfs:
            result = DFS(r_bffs, chain[-1], chain[:])
            if result:
                debug("dfs result", result)
                sc = list(max(result, key=len))[1:]
                debug("longest sub chain", sc)
                chain += sc
                debug("new chain", chain)
        yield chain

if __name__ == "__main__":
    t = int(input())
    for case in range(t):
        kids_count = int(input())
        kids = [int(i) for i in input().split()]
        bffs = {}
        r_bffs = {}
        for i in range(kids_count):
            r_bffs[i + 1] = set()
        for kid_id, bff in enumerate(kids):
            kid_id += 1
            bffs[kid_id] = bff
            r_bffs[bff] |= {kid_id}
        print(kids, bffs, r_bffs)
        debug(bffs, r_bffs)
        longest_chain = max(generate_chains(bffs, r_bffs), key=len)
        debug("longest chain for ", bffs, longest_chain)
        print(FORMAT.format(case + 1, len(longest_chain)))