Description
Problem: Cycle Breaking
Cycle breaking serves as a fundamental technique for many applications, e.g., resolving resource deadlock or
simplifying a problem instance. In graph theory, a cycle is a path where the first and the last vertices are
the same. A graph without cycles is called an acyclic graph. Given a graph G = (V, E) which may contain
cycles, we want to remove some edges to make the graph acyclic with minimum total cost (weight). Such a
problem is so-called the cycle breaking or cycle removal problem. For example, Figure 1 (a) is a weighted
undirected graph Gu with cycles. We can remove e01 and e34 to make it acyclic with total cost = 3 + 5 = 8.
For the weighted directed graph Gd in Figure 1 (b), there is only one cycle C143. So we only need to remove
e43 with total cost = 5. Cycle breaking for an (unweighted or weighted) undirected graph can be solved in
polynomial time. The problem for a weighted directed graph, however, is also known as a minimum feedback
arc set problem, which is a NP-hard problem. In this assignment, test cases contain three types of graph
instances: 1) unweighted undirected graph, 2) weighted undirected graph, and 3) weighted directed graph.
(a) weighted undirected graph (b) weighted directed graph
Figure 1: Graph with cycles.
Input
The input will be a graph with only one connected component which may contain cycles or not. The first line
of the input is a character “u” or a character “d”, which indicates the input graph is an undirected graph or
a directed graph, respectively. The second line is an integer n, denoting the total number of vertices. The
indices of these nodes will be continuous from 0 to n − 1. The third line is an integer m, denoting the total
number of edges. In the following m lines, each contains three integers i, j and w, denoting an edge from
vertex i to vertex j with weight w, −100 ≤ w ≤ 100. For test cases of unweighted undirected graph, the
weight of all edges will equal to 1. Please note that the order of vertex i and j implies the direction of the
edge in a directed graph, while it does not matter in an undirected graph. A single “0” (zero) in the input
line signifies the end of input. For undirected graph instances, 1 ≤ n ≤ 10000 and 1 ≤ m ≤ 50000000. For
directed graph instances, 1 ≤ n ≤ 5000 and 1 ≤ m ≤ 10000.
Output
The output file should report the total weight of removed edges to make the input graph acyclic, followed
by a list of these removed edges and their weights. The graph must remain connected (one connected
component) after the edges are removed. The output edges can be in arbitrary order. If the input graph
has no cycles, you should output a line with single “0” (zero) in your output file.
Here are some input/output examples:
Sample Input 1 Sample Output 1 Sample Input 2 Sample Output 2
u 8 d 5
8 0 1 3 8 4 3 5
9 3 4 5 9
0 1 3 0 1 3
0 2 5 0 2 5
1 3 10 1 4 8
1 4 8 2 5 9
2 5 9 3 1 10
3 4 5 3 5 11
3 5 11 4 3 5
3 6 12 4 7 6
4 7 6 6 3 12
0 0
Command-line Parameter:
The executable binary must be named as ‘cb” and use the following command format.
./cb
