Demo entry 5865364

friends

   

Submitted by anonymous on Aug 18, 2016 at 10:53
Language: Python. Code size: 1.3 kB.

from collections import defaultdict

def check_connection(network, first, second):
    con = make_conn(network)
    node, done  = [first], set()
    while node:
        u = node.pop(0)
        if second not in con[u]:
            if u not in done:
                done.add(u)
                node.extend(con[u])
        else:
            return True
    return False


def make_conn(network):
    con = defaultdict(set)
    for i in network:
        a,b = i.split('-', 1)
        con[a].add(b)
        con[b].add(a)
    return con


if __name__ == '__main__':
    #These "asserts" using only for self-checking and not necessary for auto-testing
    assert check_connection(
        ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
         "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
        "scout2", "scout3") == True, "Scout Brotherhood"
    assert check_connection(
        ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
         "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
        "super", "scout2") == True, "Super Scout"
    assert check_connection(
        ("dr101-mr99", "mr99-out00", "dr101-out00", "scout1-scout2",
         "scout3-scout1", "scout1-scout4", "scout4-sscout", "sscout-super"),
        "dr101", "sscout") == False, "I don't know any scouts."

This snippet took 0.00 seconds to highlight.

Back to the Entry List or Home.

Delete this entry (admin only).