SPOJ 34409 - DISGRAPH - Disconnected country

Cities of the ancient country GRAPH connected by two-way (bidirectional) roads so that from any city you can get to any other city. The Sultan wants to destroy some roads and divide the country into two separate (disconnected) areas, so that from the city of one area it was impossible to get to the city of another area. You are the Minister of transportation and your task is to minimize the number of roads that need to be destroyed. You have a lot of time and the Sultan hopes :-) that you will solve this task.

Input

The first line of input will contain one integer number 8 ≤ N ≤ 1400, number of cities in GRAPH. Follow N lines. Each line represents cities (direct neighbors) connected to the city number i (cities numbering is zero based) by one road. There will be 7 input files.

Output

One integer number. The minimum number of roads that need to be destroyed.

Example

plaintext

Input:
8
1 2
0 2 3 
0 1 3
1 2 4
3 5 6
4 6 7
4 5 7
5 6

Output:
1

Example explanation

Destroy only one road from the third city to the fourth city and Sultan will be happy.

Solution

Use Stoer-Wagner algorithm to caculate undirected graph's global min-cut. In this program, I use disjoint-set to make node-combination more easier.

Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_LINE 10000

struct edge {

  int dst;

  struct edge *next;
};

struct edge *new_edge(int dst, struct edge *next) {

  struct edge *edge = (struct edge*) malloc(sizeof(struct edge));

  edge->dst = dst;

  edge->next = next;

  return edge;
}

struct edge **parse_graph(FILE *input, int *n) {

  int src, dst;

  char cities[MAX_LINE], *ptr;
  
  struct edge **edge;

  fscanf(input, "%d", n), fgets(cities, MAX_LINE, input);

  edge = (struct edge**) malloc(sizeof(struct edge*) * (*n));

  memset(edge, 0x00, sizeof(struct edge*) * (*n));

  for(src = 0; src < *n; src++) {

    fgets(cities, MAX_LINE, input);

    for (ptr = cities; *ptr != '\0'; ) {

      for (; (*ptr != '\0') && !(*ptr >= '0' && *ptr <= '9'); ptr++);

      if ((*ptr >= '0') && (*ptr <= '9')) {

        sscanf(ptr, "%d", &dst);

        if (src != dst) {

          edge[src] = new_edge(dst, edge[src]);
				}

        for (; (*ptr != '\0') && (*ptr >= '0') && (*ptr <= '9'); ptr++);
      }
    }
  }

  return edge;
}

void free_graph(int n, struct edge **edge) {

  int src;

  struct edge *ptr;

  for (src = 0; src < n; src++) {

    for (; edge[src] != NULL; ) {

      ptr = edge[src];

      edge[src] = edge[src]->next;

      free(ptr);
    }
  }
}

int *disjoint_set_create(int n) {

  int *parent = (int*) malloc(sizeof(int) * n), i;

  for (i = 0; i < n; i++) {

    parent[i] = i;
  }

  return parent;
}

int disjoint_set_root(int *parent, int x) {

  if (parent[x] != x) {

    parent[x] = disjoint_set_root(parent, parent[x]);
  }

  return parent[x];
}

void stoer_wagner_visit(int n, struct edge **edge, int *parent,
    int *visited, int *degree, int x) {

  int i;

  struct edge *ptr;

  visited[x] = 1;

  for (i = 0; i < n; i++) {

    if (disjoint_set_root(parent, i) == x) {

      for (ptr = edge[i]; ptr != NULL; ptr = ptr->next) {

        if (disjoint_set_root(parent, ptr->dst) != x) {

          degree[disjoint_set_root(parent, ptr->dst)]++;
        }
      }
    }
  }
}

int stoer_wagner(int n, struct edge **edge) {

  int *parent = disjoint_set_create(n);

  int *visited = (int*) malloc(sizeof(int) * n);
  int *degree = (int*) malloc(sizeof(int) * n);

  int rest, i, j, u, last_2rd, last, min_cut = -1;

  for (rest = n; rest > 1; rest--) {

    memset(visited, 0x00, sizeof(int) * n);
    memset(degree, 0x00, sizeof(int) * n);

    last_2rd = -1;
    last = disjoint_set_root(parent, 0);

    stoer_wagner_visit(n, edge, parent, visited, degree, last);

    for (i = 1; i < rest; i++) {

      u = -1;

      for (j = 0; j < n; j++) {

        if (disjoint_set_root(parent, j) == j && !visited[j]) {

          if (u == -1 || degree[j] > degree[u]) {

            u = j;
          }
        }
      }

      stoer_wagner_visit(n, edge, parent, visited, degree, u);

      last_2rd = last;
      last = u;

    }

    if (min_cut == -1 || degree[last] < min_cut) {

      min_cut = degree[last];
    }

    parent[last] = last_2rd;
  }

  return min_cut;
}

int main(int argc, char **argv) {

  int n;

  struct edge **edge;

  edge = parse_graph(stdin, &n);

  printf("%d\n", stoer_wagner(n, edge));

  free_graph(n, edge);

  return 0;
}