stablemp.cpp

// Gale-Shapley algorithm for the stable marriage problem.
// madj[i][j] is the jth highest ranked woman for man i.
// fpref[i][j] is the rank woman i assigns to man j.
// Returns a pair of vectors (mpart, fpart), where mpart[i]
// gives the partner of man i, and fpart is analogous
pair<vector<int>, vector<int>>
stable_marriage(vector<vector<int>> &madj,
                vector<vector<int>> &fpref) {
  int n = madj.size();
  vector<int> mpart(n, -1), fpart(n, -1);
  vector<int> midx(n);
  queue<int> mfree;
  for (int i = 0; i < n; i++) {
    mfree.push(i);
  }
  while (!mfree.empty()) {
    int m = mfree.front();
    mfree.pop();
    int f = madj[m][midx[m]++];
    if (fpart[f] == -1) {
      mpart[m] = f;
      fpart[f] = m;
    } else if (fpref[f][m] < fpref[f][fpart[f]]) {
      mpart[fpart[f]] = -1;
      mfree.push(fpart[f]);
      mpart[m] = f;
      fpart[f] = m;
    } else {
      mfree.push(m);
    }
  }
  return make_pair(mpart, fpart);
}