On: Solving the minimum cut problem for undirected gra...

[d0mine]

Here's solution using networkx Python module:

    cutset = nx.minimum_edge_cut(G)
    for e in cutset:
        G.remove_edge(*e)
    size1, size2 = map(len, nx.connected_components(G))
    answer = size1 * size2

[guiambros → d0mine]

Same! I felt it'd be above my IQ-level, so networkx-ed it.

Here's another obvious solution:

    pos = nx.spring_layout(G)
    nx.draw_networkx_nodes(G, pos)
    nx.draw_networkx_edges(G, pos)
    nx.draw_networkx_labels(G, pos, font_size=10, font_color="white")
    plt.show()

Thankfully it was my fastest solution (after day 1). After 25 days, I wasn't in the mood of spending hours post-xmas dinner solving convoluted riddles.

[ryandv → d0mine]

Elegant. For whatever reason I elected to roll my own graph implementation in my own solution, with predictably terrible performance characteristics: using adjacency lists (instead of matrices) and BTreeSets to model "merged" vertices was not the greatest idea in hindsight..

At least it spit out the right answer after a while.