50188. Minimum Spanning Tree, part II

I'm a slow walker, but I never walk backwards.

Task Description

This is the second part of minimum spanning trees. Please refer to the first part for the description of minimum spanning trees. You will implement two methods to construct a minimum spanning tree.

Now we describe how to construct a minimum spanning tree when the flag ADD is set. First, we sort all roads by its length in ascending order. Then we start with an empty set of roads. For each iteration, we examine the road with the smallest length that we have not yet considered. If adding the road creates a cycle, we drop the road. How do we know if adding and road between city $i$ and $j$ will form a cycle? This is easy since we can check if we can go from city $i$ to city $j$, which is called a path. If there is a path before adding the road, then there will be a cycle after adding it. Now if we are certain that there will not be a cycle, we add this road into our set of minimum spanning tree. We will keep adding roads until the number of roads in the set is $N$ - 1, then we are done. Please refer to following figure for an illustration.

ADDADD

Then, we describe how to construct a minimum spanning tree when the flag REMOVE is set. We start with a map with all roads. Again we sort all roads by its length, but in descending order. Then for each iteration, we examine the longest road that we have not considered. If removing the road and the cities remains connected, we remove the road from the set of roads. Otherwise we keep it and consider the next road. We keep removing roads until the number of the roads in the map is $N$ - 1. When we finish, the set of remaining edges is a minimum spanning tree. Please refer to following figure for an illustration.

REMOVEREMOVE

Given $N$ cities and $M$ roads, you need to write a main program to construct the minimum spanning tree by one of two methods provided above depending on which flag is set, ADD or REMOVE. When using the first method, you have to print the roads you added to the MST in order. For the second method, you have to print the roads you removed from the MST in order. You should include the header mstTA.h. You can use functions and object provided by TA defined in the file mstTA.h as following:

#include <stdbool.h>
 
typedef struct mstTA {
    // TA’s implementation
} MSTTA;
 
void initTA(MSTTA *mst, int N);
void addRoadTA(MSTTA *mst, int city1, int city2, int len);
int removeRoadTA(MSTTA *mst, int city1, int city2);
bool hasPathTA(MSTTA *mst, int city1, int city2);
bool connectedTA(MSTTA *mst);

These functions work in the same way as the corresponding functions in part one.

Compile

We use the following commands to compile your code. You are not supposed to have TA's implementation and run the commands.

gcc -O2 -std=c99 -DADD main.c mstTA.c
gcc -O2 -std=c99 -DREMOVE main.c mstTA.c

However, you can still check if there are any compilation errors and warnings. Please put mstTA.h into the directory containing main.c and use the following command.

gcc -c -Wall main.c

Input Format

The first line contains two numbers. The first number $N$ is the number of cities. The second number $M$ is the number of roads. For the following $M$ lines, each line represents a road by three numbers. The first two numbers are the two adjacent cities and the last number is the length of the road. All lengths of the roads are more than zero.

  • $N \leq 10$
  • $M \leq 45$

Output Format

Please print the roads as we described above. For each road, print the two adjacent cities and the length of the road in a line separated by a space. The index of the first city should be smaller than the index of the second.

Sample

sample 1 (with ADD tag)

input

5 8
0 1 12
0 3 22
0 4 8
1 2 16
1 3 18
1 4 10
2 3 25
3 4 30

output

0 4 8
1 4 10
1 2 16
1 3 18

sample 2 (with REMOVE tag)

input

5 8
0 1 12
0 3 22
0 4 8
1 2 16
1 3 18
1 4 10
2 3 25
3 4 30

output

3 4 30
2 3 25
0 3 22
0 1 12

Discussion