Something wrong with implementation of Gale Shapley algorithm

Question

I am trying to solve this problem on spoj but continuously getting wrong answer. I dont understand what's wrong with my c++ implementation of the Gale - Shapley algorithm for the Stable Marriage Problem. Please check my code for some logical bugs.

Some data structures I have used are : 2d array 'women' and 'men' containing the preference orders, array 'm' such that m[i]=j means man i is married to woman j, similarly array w' such that w[i]=j means woman i is married to man j, 2d array 'mrg' such that mrg[i][j]=1 means i and j are married, 2d array 'pw' such that pw[i][j]=k means man j has the preference order k in i'th woman's list, similarly 2d array 'pm' such that pm[i][j]=k means woman j has the preference order k in i'th man's list. Please help me.

#include<cstdio>
#include<iostream>
using namespace std;
main() {
    int t;
    scanf("%d",&t);
    while(t--) {
        int n;
        scanf("%d",&n);
        int women[n+1][n+1],men[n+1][n+1];
        int m[n+1],w[n+1],mrg[n+1][n+1],pw[n+1][n+1],pm[n+1][n+1];
        for(int i=1;i<=n;++i) {
            m[i]=0;
            w[i]=0;
            for(int j=1;j<=n;++j) {
                mrg[i][j]=0;
                pw[i][j]=pm[i][j]=0;
            }
        }
        for(int i=1;i<=n;++i) {
            int num;
            scanf("%d",&num);
            for(int j=1;j<=n;++j) {
                scanf("%d",&women[num][j]);
                pw[num][women[num][j]]=j;
            }
        }
        for(int i=1;i<=n;++i) {
            int num;
            scanf("%d",&num);
            for(int j=1;j<=n;++j) {
                scanf("%d",&men[num][j]);
                pm[num][men[num][j]]=j;
            }
        }
        for(int i=1;i<=n;++i) {
            for(int j=1;j<=n;++j) {
                int pref=men[j][i];
                if(m[j]==0) {
                    if(w[pref]==0) {
                        w[pref]=j;
                        mrg[j][pref]=1;
                        m[j]=pref;
                    }
                    else if(pw[pref][w[pref]]>pw[pref][j]) {
                        int oldhusband=w[pref];
                        m[oldhusband]=0;
                        mrg[oldhusband][pref]=0;
                        w[pref]=j;
                        mrg[j][pref]=1;
                        m[j]=pref;
                    }
                }
                else if(pm[j][pref]<pm[j][m[j]]) {
                    if(w[pref]==0) {
                        int oldwife=m[j];
                        w[oldwife]=0;
                        mrg[j][oldwife]=0;
                        m[j]=pref;
                        w[pref]=j;
                        mrg[j][pref]=1;
                    }
                    else if(pw[pref][w[pref]]>pw[pref][j]) {
                        int oldhusband=w[pref];
                        int oldwife=m[j];
                        m[oldhusband]=0;
                        w[oldwife]=0;
                        w[pref]=j;
                        m[j]=pref;
                        mrg[oldhusband][pref]=0;
                        mrg[j][oldwife]=0;
                        mrg[j][pref]=1;
                    }
                }
            }
        }
        for(int j=1;j<=n;++j)
            cout<<j<<" "<<m[j]<<endl;
    }
    return 0;
}

Answer 1

You are not following the Gale Shapely algorithm exactly. http://en.wikipedia.org/wiki/Stable_marriage_problem

function stableMatching {
    Initialize all m ∈ M and w ∈ W to free
    while ∃ free man m who still has a woman w to propose to {
       w = m's highest ranked such woman to whom he has not yet proposed
       if w is free
         (m, w) become engaged
       else some pair (m', w) already exists
         if w prefers m to m'
           (m, w) become engaged
           m' becomes free
         else
           (m', w) remain engaged
    } }

If you look at the pseudo-code algorithm mentioned, you only need to change the partner for a woman if a higher preferred man proposes to her.

In your case you are trying to change an engaged man's partner as well if he gets a more preferred partner. According to algorithm's idea this will never happen because the woman to whom the man has been engaged to shall always be higher in preference to the current woman in consideration. Hence remove this part.

Also, the loop for men should go on untill all the men are paired (not necessarily n iterations).