【POJ 1129】Channel Allocation

【POJ 1129】Channel Allocation
폭수는 가지치기에 넣었지만...큰물문제는 훈련계획 둘째 주 마지막 문제야. 기념으로 붙여서 보내줘.
직접 부호:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#define INF 0x3f3f3f3f

using namespace std;

bool mp[26][26],vis[26];
int num[26],tp,mm,n;

void Set()//              
{
    char ch = ' ';
    int u;
    while(ch < 'A' || ch > 'Z') ch = getchar();
    u = ch-'A';
    ch = getchar();
    ch =  getchar();
    while(ch >= 'A' && ch <= 'Z')  mp[u][ch-'A'] = mp[ch-'A'][u] = 1,ch = getchar();
}

void dfs(int x)
{
    if(tp >= mm) return;//     ？。。。
    if(x == n)
    {
        mm = min(mm,tp);
        return;
    }
    int i,f = 0;
    memset(vis,0,sizeof(vis));
    for(i = 0; i < x; ++i)//             
    {
        if(mp[i][x]) vis[num[i]] = 1;
    }
    for(i = 0; i < tp; ++i)//            
    {
        if(!vis[i])
        {
            f = 1;
            num[x] = i;
            dfs(x+1);
        }
    }
    if(!f)//               
    {
        num[x] = tp++;
        dfs(x+1);
    }
}

int main()
{
    int i,j;
    while(~scanf("%d",&n) && n)
    {
        memset(mp,0,sizeof(mp));
        for(i = 0; i < n; ++i) Set();

        tp = 0;
        mm = INF;

        dfs(0);
        printf("%d channel",mm);
        if(mm-1) putchar('s');
        puts(" needed.");
    }
    return 0;
}