# include <iostream>
using namespace std;
const int MAX=4;
bool ChangFriend(const int libLady[][MAX+1], int v, int oldF, int newF); //判断是否要换男友

int main()
{
    int libMan[MAX][MAX]={{2,1,3,0},{0,2,3,1},{2,3,1,0},{1,3,2,0}}; //存储男士所喜欢的女士需要的排列表
    int libLady[MAX][MAX+1]={{0,3,1,2,MAX},{1,3,2,3,MAX},{0,2,3,1,MAX},{1,0,3,2,MAX}};//存储女士所喜欢的男士序号的排列表
    int man[MAX+1]={0};a
    int lady[MAX]={MAX,MAX,MAX,MAX};
    int i=0;

    while (i<MAX)
    {
        int v=libMan[i][man[i]];//i号男喜欢v号女
        if (i==lady[v])//i号男就是v号女当前男友，跳过，处理下一个男士
            i++;
        else if (ChangeFriend(libLady,v,lady[v],i))//若i号男比v号女当前男友优秀，则v抛弃其前男友，重新选择i
        {
            int t=lady[v];//存储前男友序号
            man[lady[v]]++;//抛弃前男友， 即前男友选择其“次喜欢女”
            lady[v]=i;//选择i号男为新男友
            if(t>i)//前男友序号t在新男友i之后，则今后顺序前行可以处理t
                i++;//处理下一个男士
            else //前男友序号t在新男友i之前，返回t，否则会漏掉t
                i=t;
        }
        else //继续处理i号男的“此喜欢女”
            man[i]++;
    }

    for (int i=0; i<MAX; i++)//输出每位男士追求女士的次数
        cout<<man[i]+1<<",";
    cout<<end;

    for(int i=0; i<MAX; i++)//输出每位男士的妻子的序号
        cout<<libMan[i][man[i]]<<",";
    cout<<end;

    for(int i=0; i<MAX; i++)//输出每位女士的丈夫的序号
        cout<<lady[i]<<",";
    cout<<end;
    system("pause");
    return 0;
}

bool ChangeFriend(const int libLady[][MAX+1], int v, int oldF, int newF)//判断是否需要换男友
{
    for(int i=0; i<MAX; i++)
    {
        if(libLady[v][i]==oldF)
        {
            oldF=i;
            break;
        }
    }
    for (int i=0; i<MAX; i++)
    {
        if(libLady[v][i]==newF)
        {
            newF=i;
            break;
        }
    }
    return (oldF>newF);
}