Advent of Code 2024 day 23 part 2

from collections import defaultdict
from sys import argv


def parse(src):
    for line in src.splitlines():
        if line == '':
            continue
        first, second = line.split('-', 1)
        yield first.strip(), second.strip()


def make_graph(connections):
    graph = defaultdict(set)
    for first, second in connections:
        graph[first].add(second)
        graph[second].add(first)
    return graph


def bron_kerbosch(graph, r, p, x):
    def degree(node):
        return len(graph[node])

    if len(p) == 0 and len(x) == 0:
        yield r
    else:
        pivot = max(p | x, key=degree)
        for v in p - graph[pivot]:
            neighbors = graph[v]
            yield from bron_kerbosch(
                graph, r | {v}, p & neighbours, x & neighbors)
            p.remove(v)
            x.add(v)


def main(connections):
    graph = make_graph(connections)
    clique = max(bron_kerbosch(graph, set(), set(graph.keys()), set()),
                 key=len)
    return ','.join(sorted(clique))


if __name__ == '__main__':
    print(main(parse(open(argv[1]).read())))