Since the AoC specifies the min-cut for you I found it was simpler to take advantage of that.
I picked two random vertices and found the shortest path between them 3 times, cutting each vertex after each iteration. If after doing that I couldn't find a path between the two vertices then I had successfully partitioned the graph in two. Otherwise that meant I picked two vertices in the same partition and I reset the graph and randomly picked a different vertex.
Ended up being very quick to run, and easy to implement.
I picked two random vertices and found the shortest path between them 3 times, cutting each vertex after each iteration. If after doing that I couldn't find a path between the two vertices then I had successfully partitioned the graph in two. Otherwise that meant I picked two vertices in the same partition and I reset the graph and randomly picked a different vertex.
Ended up being very quick to run, and easy to implement.