POJ 3487 - 혼인 시스템 안정

#include <cstdio>
#include <cstring>
#include <cctype>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

const int NN=128;
const int INF=0x3fffffff;

int n,cnt1,cnt2,hash[NN],tmpf[NN],cur[NN],num[NN],tag[NN],w[NN][NN];
char id[NN];
bool single[NN];
vector<int> fav[NN];

int get()
{
    int x;
    char ch=getchar();
    while (!isalpha(ch)) ch=getchar();
    if (islower(ch))
    {
        x=ch-'a';
        if (!hash[x])
        {
            hash[x]=++cnt1;
            id[cnt1]=ch;
        }
    }
    else
    {
        x=ch-'A'+26;
        if (!hash[x])
        {
            hash[x]=++cnt2;
            id[cnt2]=ch;
        }
    }
    return hash[x];
}
void init()
{
    scanf("%d",&n);
    cnt1=0;
    cnt2=n;
    memset(hash,0,sizeof(hash));
    for (int i=1; i<=n*2; i++) //    1~n ,    n+1~2*n 
    {
        int x=get();
        fav[x].clear();
        tag[x]=0;
        w[x][0]=INF;
        single[x]=true; //    
    }
    for (int i=1; i<=n*2; i++)
    {
        int x=get();
        for (int j=1; j<=n; j++)
        {
            int y=get();
            w[x][y]=j;
            fav[x].push_back(y);
        }
    }
}

int main()
{
    int cas,x,y;
    scanf("%d",&cas);
    while (cas--)
    {
        init();
        for (int k=0; k<n;) //k           
        {
            memset(num,0,sizeof(num));
            memset(tmpf,0,sizeof(tmpf));
            int sum=0;
            for (int i=1; i<=n; i++)
            {
                if (single[i] && tag[i]<fav[i].size())//      
                {
                    int x=fav[i][tag[i]++]; //       x     
                    num[x]++; // x     +1
                    sum++;    //    +1
                    if (w[x][i]<w[x][tmpf[x]]) tmpf[x]=i;//     ?
                }
            }
            if (sum==0) break; //     
            for (int i=n+1; i<=n*2; i++) //       i
            {
                if (num[i]==0) continue; //      i  
                if (single[i]) //     ,   ,    
                {
                    single[tmpf[i]]=false;
                    single[i]=false;
                    cur[tmpf[i]]=i; //    
                    cur[i]=tmpf[i];
                    k++;            //      
                }
                else if (w[i][tmpf[i]]<w[i][cur[i]])
                //      BF        
                {
                    single[cur[i]]=true; //     
                    single[tmpf[i]]=false; //     
                    cur[tmpf[i]]=i;
                    cur[i]=tmpf[i];
                }
            }
        }
        for (int i=1; i<=n; i++)
        {
            if (!single[i])  printf("%c %c
",id[i],id[cur[i]]);
        }
        printf("
");
    }
    return 0;
}