3 ms·
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
by d0mine 3y ago
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
- ryandv 3y agoElegant. 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.
- guiambros 3y agoSame! 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.