Description
Given a graph, write a Java program that finds the minimum cut by
implementing the randomized min-cut algorithm. You should also implement
Union-by-Rank and Path Compression for the disjoint set operations (Union and
Find ops) to find a minimum weight spanning tree with Kruskal’s algorithm.
Input
The input consists of a sequence of 20 test cases. Each test case consists of m
+ 1 lines, where m is the number of edges in the graph. In the first line, two
integers n and m are given, where n is the number of vertices in the graph. The
each of the next m lines has two integers, indicating the endpoints of the edge.
The labels of the vertices are 0, 1, 2, …, n-1. The maximum value of n is 1,000.
Output
There should be one line of output for each test case in the input file. For each
test case, print out a single integer, indicating the size of the minimum cut of
the graph found by the randomized Min-Cut algorithm.
2
Sample Input
20 // the no of test cases =20
8 11 // n =8, m =11, test case #1
0 1
0 4
1 4
1 5
4 5
2 3
2 5
2 6
3 6
3 7
6 7
8 15 // n =8, m =15, test case #2
0 1
0 3
0 4
1 2
1 3
1 4
2 5
2 6
2 7
3 4
4 5
4 6
5 6
5 7
6 7
…
Sample Output
1 // test case #1
3 // test case #2
…
Test case #1 example
