A c++ program to determine a cut tree for an undirected graph

It will use minimum cut- maximum flow i.e Ford- Fulkerson Algorithm to get the final output.

It should work for larger inputs typed by the user. The program should work till the number of vertices are 3000 and number of edges are 10000.

The graph can also be treated simply as a symmetric directed graph.

In the output cut tree, the smallest capacity on the unique path between vertices s and t gives the capacity of the minimum cut when s and t are used as the source and sink for a network flow algorithm.

The user will give input as

In the first line , there will be two values, n amd m, giving number of vertices and edges.

The next m lines will each contain three integers. The first two, the vertices incident to an edge, will be in the range 0..n-1. The third value will be a positive capacity.

For example, users input will be

6 8

0 1 2

0 2 1

0 4 2

1 2 4

2 3 5

3 4 5

4 1 2

4 5 5

Output

the number of output lines will be n-1.

Each line will have two vertices incident to an edge in the computes cut tree, followed by its capacity.

For example, output for the above input will be shown as

1 2 8

2 0 5

3 2 9

4 3 9

5 4 5

Another example,

Users input

15 24

0 1 20

0 2 20

1 3 12

1 4 8

2 5 15

2 6 5

3 4 4

3 7 8

4 7 18

5 4 2

5 6 10

5 9 3

6 10 17

7 8 11

7 11 15

8 4 4

8 11 7

9 6 2

9 11 1

10 11 17

11 12 43

12 13 43

13 11 3

13 14 40

output

1 0 40

2 0 40

3 0 24

4 7 36

5 0 30

6 0 34

7 0 40

8 7 22

9 0 6

10 0 34

11 7 40

12 11 46

13 12 46

14 13 40