Stable Marriage Problem.cpp

/* Stable Marriage Problem */
/* Author : M. A. Rafsan Mazumder */

#include <bits/stdc++.h>

using namespace std;

#define MAX 205
int N;
int prefer[MAX][MAX];
int wPartner[MAX];
int iterate[MAX];

//Input is a 2D matrix of size (2*N)*N where N is the number of women
//or men. Rows from 0 to N-1 represent preference lists of men and
//rows from N to 2*N – 1 represent preference lists of women. So men
//are numbered from 0 to N-1 and women are numbered from N to 2*N – 1.

bool wPreferM1overM(int w, int m1, int m)
{
    for(int i=0; i<N; i++){
        if(prefer[w][i] == m1) return true;
        if(prefer[w][i] == m) return false;
    }
}

void stableMarriage()
{
    bool mFree[N]; //if mFree[i] is true, then i is not married yet
    memset(mFree, true, sizeof mFree);
    memset(wPartner, -1, sizeof wPartner);
    memset(iterate, 0, sizeof iterate);

    int freeCount = N;
    while(freeCount > 0){
        int m;
        for(int i=0; i<N; i++){
            if(mFree[i]) m = i;
        }
        for(int i=iterate[m]; i<N && mFree[m] == true; i++){
            int w = prefer[m][i];

            if(wPartner[w] == -1){
                wPartner[w] = m;
                mFree[m] = false;
                freeCount--;
            }
            else {
                int m1 = wPartner[w];
                if(wPreferM1overM(w, m1, m) == false){
                    wPartner[w] = m;
                    mFree[m] = false;
                    mFree[m1] = true;
                }
            }
            iterate[m]++;
        }
    }
}

int main()
{
    freopen("in.txt", "r", stdin);
    scanf("%d", &N);
    for(int i=0; i<2*N; i++){
        for(int j=0; j<N; j++) scanf("%d", &prefer[i][j]);
    }
    stableMarriage();
    for(int i=N; i<2*N; i++) printf("%d %d\n", i, wPartner[i]);

}