general-matching.cpp

// Unweighted general matching.
// Vertices are numbered from 1 to V.
// G is an adjlist.
// G[x][0] contains the number of neighbours of x.
// The neigbours are then stored in G[x][1] ..
// G[x][G[x][0]]. Mate[x] will contain the matching node for
// x. V and E are the number of edges and vertices. Slow
// Version (2x on random graphs) of Gabow's implementation
// of Edmonds' algorithm (O(V^3)).
const int MAXV = 250;
int G[MAXV][MAXV];
int VLabel[MAXV];
int Queue[MAXV];
int Mate[MAXV];
int Save[MAXV];
int Used[MAXV];
int Up, Down;
int V;

void ReMatch(int x, int y) {
  int m = Mate[x];
  Mate[x] = y;
  if (Mate[m] == x) {
    if (VLabel[x] <= V) {
      Mate[m] = VLabel[x];
      ReMatch(VLabel[x], m);
    } else {
      int a = 1 + (VLabel[x] - V - 1) / V;
      int b = 1 + (VLabel[x] - V - 1) % V;
      ReMatch(a, b);
      ReMatch(b, a);
    }
  }
}

void Traverse(int x) {
  for (int i = 1; i <= V; i++)
    Save[i] = Mate[i];
  ReMatch(x, x);
  for (int i = 1; i <= V; i++) {
    if (Mate[i] != Save[i])
      Used[i]++;
    Mate[i] = Save[i];
  }
}

void ReLabel(int x, int y) {
  for (int i = 1; i <= V; i++)
    Used[i] = 0;
  Traverse(x);
  Traverse(y);
  for (int i = 1; i <= V; i++) {
    if (Used[i] == 1 && VLabel[i] < 0) {
      VLabel[i] = V + x + (y - 1) * V;
      Queue[Up++] = i;
    }
  }
}

// Call this after constructing G
void Solve() {
  for (int i = 1; i <= V; i++)
    if (Mate[i] == 0) {
      for (int j = 1; j <= V; j++)
        VLabel[j] = -1;
      VLabel[i] = 0;
      Down = 1;
      Up = 1;
      Queue[Up++] = i;
      while (Down != Up) {
        int x = Queue[Down++];
        for (int p = 1; p <= G[x][0]; p++) {
          int y = G[x][p];
          if (Mate[y] == 0 && i != y) {
            Mate[y] = x;
            ReMatch(x, y);
            Down = Up;
            break;
          }
          if (VLabel[y] >= 0) {
            ReLabel(x, y);
            continue;
          }
          if (VLabel[Mate[y]] < 0) {
            VLabel[Mate[y]] = x;
            Queue[Up++] = Mate[y];
          }
        }
      }
    }
}

// Call this after Solve(). Returns number of edges in
// matching (half the number of matched vertices)
int Size() {
  int Count = 0;
  for (int i = 1; i <= V; i++)
    if (Mate[i] > i)
      Count++;
  return Count;
}