50187. Minimum Spanning Tree, part I

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

Task Description

We are going to design an object MST and implement the functions for minimum spanning trees.

There are $N$ cities indexed from 0 to $N$ - 1 and $M$ roads. Every road has two adjacent cities and all roads have different lengths. A set of roads connect the cities if we can go from any city to any other cities by going through them. A set of roads is a minimum spanning tree if they connect the cities with the minimum total length of roads. Please refer to following figure for an illustration. Following is the minimum spanning tree, where the roads not selected into the tree is in grey. Note that there are exactly $N$ - 1 edges in a minimum spanning tree.

minimum spanning treeminimum spanning tree

You need to design an object MST and implement five functions init, addRoad, removeRoad, connected and hasPath. We will use init to initialize a MST object. Function addRoad adds a road that connects $city1$ and $city2$, and the length of the road $len$ into the MST. Function removeRoad removes the road between two given cities $city1$, and $city2$ and returns the length of the removed road. If there is no road between two given cities, you should return 0. Function connected returns true if the cities are connected by this MST. Function hasPath returns true if you can go from $city1$ to $city2$ through the MST.

The interfaces of structure and functions are defined in mst.h. Following is a template for mst.h. You should implement these functions in mst.c.

#include <stdbool.h>
 
typedef struct mst {
    // design your object here
} MST;
 
void init(MST *mst, int N);
void addRoad(MST *mst, int city1, int city2, int len);
int removeRoad(MST *mst, int city1, int city2);
bool hasPath(MST *mst, int city1, int city2);
bool connected(MST *mst);

You can use the following main function from main.c to test your functions and structure.

#include <stdio.h>
#include "mst.h"
 
int main() {
  int n, m;
  MST mst;
  scanf("%d%d", &n, &m);
  init(&mst, n);
  for(int i = 0, j, k, l, s; i < m; i++) {
    scanf("%d", &j);
    switch(j) {
      case 0:
        scanf("%d%d%d", &k, &l, &s);
        addRoad(&mst, k, l, s);
        printf("Add road.\n");
        break;
      case 1:
        scanf("%d%d", &k, &l);
        s = removeRoad(&mst, k, l);
        printf("Remove road of length %d.\n", s);
        break;
      case 2:
        s = connected(&mst);
        printf("MST is %sconnected.\n", s ? "" : "not ");
        break;
      case 3:
        scanf("%d%d", &k, &l);
        s = hasPath(&mst, k, l);
        printf("There is %sa path.\n", s ? "" : "not ");
        break;
    }
  }
        return 0;
}

Input Format

Each line contains a query. The first number is the query type.

For query type 0, the query is for addRoad. The rest three numbers are the two adjacent cities and the length of the road to add.

For query type 1, the query is for removeRoad. The rest two numbers are the two adjacent cities of the road to remove.

For query type 2, the query is for connected.

For query type 3, the query is for hasPath. The rest two number are the two cities to exam if there is a path between them through the MST.

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

Output Format

For each query we will output one line.

For query type 0, we print “Add road.”

For query type 1, we print “Remove road of length $i$.”, where $i$ is the return value of removeRoad.

For query type 2, we print “MST is connected.” when the MST is connected and print “MST is not connected.” when it is not.

For query type 3, we print “There is a path.” when there is a path between given two cities and print “There is not a path.” when there isn’t.

Sample 1

input

5 11
0 0 3 76
3 1 2
0 2 4 46
3 0 3
0 1 3 66
0 2 3 100
2
0 1 2 45
2
1 2 4
2

output

Add road.
There is not a path.
Add road.
There is a path.
Add road.
Add road.
MST is connected.
Add road.
MST is connected.
Remove road of length 46.
MST is not connected.

Discussion