2023/day25.c

   1 #include <stdio.h>
   2 #include <stdbool.h>
   3
   4 /* https://en.wikipedia.org/wiki/Stoer%E2%80%93Wagner_algorithm
   5  * Modified by the fact that we KNOW mincut is 3, and we instead
   6  * want the count of nodes on each side of the cut.  So, instead
   7  * of running the algorithm to the end, we track an additional
   8  * node-count metric, and stop when we hit the desired mincount.
   9  */
  10
  11 #define maxn 1500 /* 1484 in my input */
  12 int map[26*26*26]; /* map input 3-alpha into node number */
  13 int edge[maxn][maxn]; /* weighted adjacency matrix */
  14 int dist[maxn]; /* weight of each node */
  15 int count[maxn]; /* number of nodes merged together */
  16 bool vis[maxn]; /* true if vertex visited */
  17 bool bin[maxn]; /* true for vertex deleted by merging */
  18 int n; /* vertex count; for convenience first vertex is 1 */
  19
  20 int contract(int *s, int *t)
  21 {
  22   int i, j, k, mincut, maxc;
  23   for (i = 1; i <= n; i++) {
  24     dist[i] = vis[i] = 0;
  25   }
  26   for (i = 1; i <= n; i++) {
  27     k = -1; maxc = -1;
  28     for (j = 1; j <= n; j++)
  29       if (!bin[j] && !vis[j] && dist[j] > maxc) {
  30         k = j; maxc = dist[j];
  31       }
  32     if (k == -1)
  33       return mincut;
  34     *s = *t; *t = k;
  35     mincut = maxc;
  36     vis[k] = true;
  37     for (j = 1; j <= n; j++)
  38       if (!bin[j] && !vis[j])
  39         dist[j] += edge[k][j];
  40   }
  41   return mincut;
  42 }
  43
  44 int stoer_wagner(void)
  45 {
  46   int i, j, s, t, ans;
  47   for (i = 1; i < n; i++) {
  48     ans = contract(&s, &t);
  49     bin[t] = true;
  50     if (ans == 3) {
  51       printf("%d %d %d %d\n", s, t, count[s], count[t]);
  52       ans = count[s] + count[t];
  53       return ans * (n - ans);
  54     }
  55     count[s] += count[t];
  56     for (j = 1; j <= n; j++)
  57       if (!bin[j])
  58         edge[s][j] =  (edge[j][s] += edge[j][t]);
  59   }
  60   return 0;
  61 }
  62
  63 int value(char name[3]) {
  64   int v = (name[0]-'a')*26*26 + (name[1]-'a')*26 + name[2]-'a';
  65   if (!map[v]) {
  66     count[n] = 1;
  67     map[v] = ++n;
  68   }
  69   return map[v];
  70 }
  71
  72 int main(int argc, char **argv)
  73 {
  74   char name[3];
  75   int a, b;
  76   FILE *in;
  77
  78   if (argc != 2) {
  79     printf("usage: %s day25.input\n", argv[0]);
  80     return 1;
  81   }
  82   in = fopen(argv[1], "r");
  83   if (!in) {
  84     printf("failure to open file\n");
  85     return 1;
  86   }
  87   while (fscanf(in, "%3c:", name) == 1) {
  88     a = value(name);
  89     while (getc(in) == ' ') {
  90       fscanf(in, "%3c", name);
  91       b = value(name);
  92       edge[a][b] = edge[b][a] = 1;
  93     }
  94   }
  95   printf("%d\n", stoer_wagner());
  96   return 0;
  97 }