STABLE MARRIAGE PROBLEM

• Problem Description

  
  There are given n men and n women. Each woman ranks all men in order of her preference (her first choice, her second choice, and so on). Similarly, each man sorts all women according to his preference. The goal is to arrange n marriages in such a way that if a man m prefers some woman w more than his wife, and w prefers m more then her husband a new marriage occurs between w and m. If w prefers her husband more, then she stays married to him. This problem always has a solution and your task is to find one.
  
  Input
  
  The first line contains a positive integer t<=100 indicating the number of test cases. Each test case is an instance of the stable marriage problem defined above. The first line of each test case is a positive integer n<=500 (the number of marriages to find). The next n lines are the woman's preferences: ith line contains the number i (which means that this is the list given by the ith woman) and the numbers of men (the first choice of ith woman, the second choice,...). Then, the men's preferences follow in the same format.
  
  Output
  
  For each test case print n lines, where each line contains two numbers m and w, which means that the man number m and the woman number w should get married

• CODING ARENA

• #include <stdio.h>

  int men[10][10];

  int women[10][10];

  int mmark[10]={0};

  int mc[10]={0};

  int wc[10]={0};

  int inp()

  {

    int n=0;

    int ch=getchar();

    while(!(ch>='0'&&ch<='9'))

      ch=getchar();

    while(ch>='0'&&ch<='9')

      n=(n<<3)+(n<<1)+ch-'0',ch=getchar();

    return n;

  }

  int func1(int w,int m,int m1,int n)

  {

    int i;

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

    {

      if(women[w][i]==m)

        return 1;

      else

        if(women[w][i]==m1)

          return 0;

    }

    return 0;

  }

  void stablemarriage(int n)

  {

    int i,c;

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

    {

      mmark[i]=0;

      wc[i]=-1;

    }

    c=n;

    while(c>0)

    {

      int m;

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

        for(i=1;i<=n&&mmark[m]==0;i++)

        {

          int w=men[m][i];

          if(wc[w]==-1)

          {

            wc[w]=m;

            mmark[m]=1;

            c--;

          }

          else

          {

            int m1=wc[w];

            if(func1(w,m,m1,n))

               {

                 wc[w]=m;

                 mmark[m]=1;

                 mmark[m1]=0;

               }

          }

        }

    }

  }

  int main()

  {

    int n,t,i,j;

    t=inp();

    while(t--)

    {

      n=inp();

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

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

          women[i][j]=inp();

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

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

          men[i][j]=inp();

      stablemarriage(n);

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

      {

        mc[wc[i]]=i;

      }

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

        printf("%d %d\n",i,mc[i]);

    }

  return 0;

  }

• Test Case 1

  
  Input (stdin)

  2
  
  4
  
  1 4 3 1 2
  
  2 2 1 3 4
  
  3 1 3 4 2
  
  4 4 3 1 2
  
  1 3 2 4 1
  
  2 2 3 1 4
  
  3 3 1 2 4
  
  4 3 2 4 1
  
  7
  
  1 3 4 2 1 6 7 5
  
  2 6 4 2 3 5 1 7
  
  3 6 3 5 7 2 4 1
  
  4 1 6 3 2 4 7 5
  
  5 1 6 5 3 4 7 2
  
  6 1 7 3 4 5 6 2
  
  7 5 6 2 4 3 7 1
  
  1 4 5 3 7 2 6 1
  
  2 5 6 4 7 3 2 1
  
  3 1 6 5 4 3 7 2
  
  4 3 5 6 7 2 4 1
  
  5 1 7 6 4 3 5 2
  
  6 6 3 7 5 2 4 1
  
  7 1 7 4 2 6 5 3
  
  

  Expected Output

  1 3
  
  2 2
  
  3 1
  
  4 4
  
  1 4
  
  2 5
  
  3 1
  
  4 3
  
  5 7
  
  6 6
  
  7 2

• Test Case 2

  
  Input (stdin)

  1
  
  4
  
  1 4 3 1 2
  
  2 2 1 3 4
  
  3 1 3 4 3
  
  4 4 3 1 2
  
  1 3 2 4 1
  
  2 2 1 1 2
  
  3 3 1 2 4
  
  4 3 2 4 1
  
  

  Expected Output

  1 3
  
  2 2
  
  3 1
  
  4 4