bipirating

bipirate.py

#!/usr/bin/env python

import codecs
import os
import sys
from collections import defaultdict
from pprint import pprint

STATE_NAME, STATE_ACCUSATION = 0, 1

class Graph(object):
    def __init__(self): self.ve = defaultdict(set)
    def add(self, a, b): self.ve[a].add(b); self.ve[b].add(a)
    def display(self): pprint(self.ve)

    def bifrucate(self):
        """The main algorithm: run DFS and count the number of
        elements in each bipartite set."""

        # Pick an arbitrary root and start DFS. It doesn't matter
        # where because the graph is connected.
        if not self.ve: return [0, 0]
        root, edges = self.ve.iteritems().next()

        # DFS!
        visited, tovisit = set(), set()
        tovisit.add((root, True))
        counts = [0, 0]
        while tovisit:
            v, depth = tovisit.pop()
            if v in visited: continue
            visited.add(v)
            tovisit.update([(e, not depth) for e in self.ve[v]])

            # Every DFS visit has an odd or even parity, corresponding
            # to the two bipartite components. Count them here.
            counts[depth] += 1

        counts.sort(reverse=True)
        return counts

def main(handle):
    graph = Graph()

    # Read in how many vertices there are. I'm using Python's data
    # structures, which resize, so I don't really need this.
    n = int(handle.readline())

    # And now, a simple two-state machine to parse the files.
    state = STATE_NAME
    name, m = None, 0

    for line in handle:
        line = line.strip()

        # NAME state: read in the accuser and the number of
        # accusations. Move to the ACCUSATION state.
        if state == STATE_NAME:
            name, count = line.split()
            m = int(count)
            if m > 0: state = STATE_ACCUSATION

        # ACCUSATION state: read in the accusee, decrement the number
        # of accusations. Add an edge on the graph. On zero
        # accusations, move to the NAME state.
        elif state == STATE_ACCUSATION:
            graph.add(name, line)
            m -= 1
            if m == 0:
                state = STATE_NAME

    m, n = graph.bifrucate()
    print('%s %s' % (m, n))

if __name__ == '__main__':
    main(codecs.open(sys.argv[1], 'r', 'utf8'))