uva_259

#include <iostream>
#include <cstdio>
#include <stdio.h>
#include <string>
#include <cstring>
using namespace std;
bool DFS(int);
int bipartite_matching();

int nx, ny;             // X的點數目、Y的點數目
int mx[100], my[100];   // X各點的配對對象、Y各點的配對對象
bool vy[100];           // 記錄Graph Traversal拜訪過的點
bool adj[100][100];     // 精簡過的adjacency matrix



int main(int argc, const char * argv[]) {
      char input_table[1000];
    int num;
    int now_top;
        bool going=true;

    memset(input_table,0,sizeof(input_table));
    memset(adj,false,sizeof(adj));
    memset(my,-1,sizeof(my));
    memset(mx,-1,sizeof(mx));
    memset(vy,false,sizeof(vy));

    now_top=0;
    ny=10;
        //string line;
        char line[205];
    now_top=0;

        while(going){
            //初始化
         now_top=0;
      nx=0;
      memset(vy,false,sizeof(vy));
        memset(my,-1,sizeof(my));
            memset(mx,-1,sizeof(mx));
      memset(input_table,0,sizeof(input_table));
      memset(adj,false,sizeof(adj));


        while(1){
                    if(!fgets(line,200,stdin)){
                        going=false;
                        break;
                    }
                    //printf("%c\n",line[0]);
            if(line[0]=='\n'){
                //end of line
                         break;
            }
            num = line[1]-'0';
            nx+=num;
         //紀錄第幾個y點是哪一個application
         for(int i=now_top;i<(now_top+num);i++){
             input_table[i]=line[0];
             for(int j=3;line[j]!=';';j++){
                 adj[i][(line[j]-'0')]=true;
             }
         }
         now_top+=num;
        }
            int a;
      //printf("bipartitie_matching:%d\n",a=bipartite_matching());
      a=bipartite_matching();
      if(a==nx){
          for(int i=0;i<10;i++){
               if(input_table[my[i]]==0){
                 printf("%c",'_');
             }else{
                 printf("%c",input_table[my[i]]);
             }
        }
        printf("\n");
      }else{
           printf("!\n");
      }

        }
        //printf("\n");

    return 0;
}

bool DFS(int x)
{
    for (int y=0; y<ny; ++y)
        if (adj[x][y] && !vy[y])
        {
            vy[y] = true;

            // 找到擴充路徑
            //這個if有點厲害，一邊調整mx與my，一邊往下找尋augmenting path
            if (my[y] == -1 || DFS(my[y]))
            {
                mx[x] = y; my[y] = x;
                return true;
            }
        }
    return false;
}

int bipartite_matching()
{
    // 全部的點初始化為未匹配點。
    memset(mx, -1, sizeof(mx));
    memset(my, -1, sizeof(my));

    // 依序把X中的每一個點作為擴充路徑的端點，
    // 並嘗試尋找擴充路徑。
    int c = 0;
    for (int x=0; x<nx; ++x)
        //      if (mx[x] == -1)    // x為未匹配點，這行可精簡。
    {
        // 開始Graph Traversal
        memset(vy, false, sizeof(vy));
        if (DFS(x)) c++;
    }
    return c;
}