**Stable Matching : **

Stable marriage simply works on preference like seeking a better opportunities of matching ,

Finding out best choice from many choice can be done with stable marriage ,the working algorithm is

# Gale Shapley Algorithm

in youtube,there are many videos,one of them is

There are some problems on this

One of them Codechef

## +View Code

/*

Prog : Stable Marriage

User : Avijeet

Lang : C++

*/

const int N=505;

#include<bits/stdc++.h>

int pos[N][N],wP[N][N],mP[N][N],up[N],out[N];

using namespace std;

int main()

{

int i,j,w,m,t;

queue <int > mfree;

cin>>t;

while(t–)

{

int n;

cin>>n;

for(i=1;i<=n;i++) { cin>>w;

for(j=1;j<=n;j++) cin>>wP[w][j];

}

for(i=1;i<=n;i++) { cin>>m;

for(j=1;j<=n;j++) cin>>mP[m][j];

}

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

pos[i][wP[i][j]]=j;

//position of man in PL of each woman

//pos[w][m]=i if wP[w][i]=m

memset(out,0,(n+1)*sizeof(int));

for(i=1;i<=n;i++)

{

mfree.push(i);

up[i]=1;

}

while(!mfree.empty())

{

m=mfree.front();

w=mP[m][up[m]++];

if(out[w]==0)

{

out[w]=m;

mfree.pop();

}

else if(pos[w][m]<pos[w][out[w]])

{

mfree.pop();

mfree.push(out[w]);

out[w]=m;

}

}

for(w =1;w<=n;w++)

cout<<out[w]<<” “<<w<<endl;

}

}