Poj Solution 1129

http://poj.org/problem?id=1129

 import java.util.*;
import java.io.*;
/*
 *����������ŵ7��䡣��һ������ͼ��Ϊÿ����������ɫ��Ҫ���������ڵĶ�����ɫ��ͬ��
 * �����ٵ���ɫ���Ƕ���?
 *������������ɫ���?ֱ��ö����ɫ��+DFS������DFS�DZ�fö��ÿ�����ɫ���Ա��ҵ�һ����н⡣ 
 */
public class Main{
    
    public static int[][] g=new int[26][26];
    
    public static int solve(int n){
        int i,j,cnum;
        boolean tag=true;
        // �ޱ�ͼֻ��1ɫ����
        for(i=0;i< n && tag;i++){
            for(j=i+1;j< n && tag;j++){
                if(g[i][j]==1) 
                    tag=false;
            }
           }
        if(tag) 
            return 1;
        
        for(cnum=2;cnum<=4;cnum++)    // ö�ٴ�+dfs
        {
            int[] x=new int[n];
            Arrays.fill(x,-1);
            if(DFS(x,0,cnum,n)) 
                return cnum;
        }
        return -1;
    }
    
    //DFS�ĸ��Ӷ�����ɫ��^������(4^26�����п����Լ�֦����˺ܶ��֧) 
    public static boolean DFS(int[] x,int vnum, int cnum,int n){
        if(vnum == n) return true;    // v�Ķ��㶼��ɫ�����н�
        for(int i=0;i< cnum;i++){    // ���ij���û����ɫ�������һ��
            x[vnum] = i;
            if(check(vnum,x,i,n))         
                if(DFS(x,vnum+1,cnum,n)) // �Ϸ���ö����һ���
                    return true;
        }
        return false;
    }

    // �ж����ڵĶ����Ƿ���Ϳ��������ɫ
    public static boolean check(int vnum,int[] x,int t,int n){
        boolean find=true;
        for(int i=0;i< n && find;i++){
            if(g[vnum][i]==1 && x[i]==t)
                find=false;
        }
        return find;
    }
    
    public static void main(String rgs[]) throws Exception
    {  
        Scanner cin = new Scanner(new BufferedInputStream(System.in));
        int i,j,n=cin.nextInt();
        while(n!=0){            
            for(i=0;i< n;i++)
                Arrays.fill(g[i],0);        
            for(i=0;i< n;i++){
                String s = cin.next();
                for(j=2;j< s.length();j++)
                    g[i][s.charAt(j)-'A']=1;
            }
            int count=solve(n);
            if(count==1)
                System.out.println(count+" channel needed.");
            else
                System.out.println(count+" channels needed.");
            n=cin.nextInt();
        }
    }
}