四色定理+dfs（poj 1129）

　　题目：Channel Allocation

　　题意：要求A:BCD，A与B,C,D都不相同，求不同的值，典型的四色定理；

　　

#include <iostream>

#include <algorithm>

#include <stdlib.h>

#include <time.h>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define zero_(x,y) memset(x , y , sizeof(x))

#define zero(x) memset(x , 0 , sizeof(x))

#define MAX(x) memset(x , 0x3f ,sizeof(x))

#define swa(x,y) {LL s;s=x;x=y;y=s;}

using namespace std ;

#define N 105

const double PI = acos(-1.0);

typedef long long LL ;

int mapp[N][N], color[N];

int col,flag;

int n;

string s;

bool ok(int i){

    for(int j = ; j <= ; j++){

        if(!mapp[i][j]) continue;

        if(color[i] == color[j]) return false;

    }

    return true;

}

void dfs(int num){

    if(num > n) {flag = ; return ;}

    for(int i = ; i <= col; i ++){

        color[num] = i;

        if(ok(num))

            dfs(num+);

        color[num]= ;    ///记得回溯时要清零啊！！！

    }

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    while(cin>>n && n){

        flag = ;

        zero(mapp);

        for(int i = ; i< n;i++){

            cin>>s;

            int k = s.size();

            int x,y;

            for(int j = ;j< k;j++){

                x = s[] - 'A' +;

                y = s[j] - 'A' +;

                mapp[x][y] = mapp[y][x] = ;

            }

        }

        for(col = ; col <= ; col++){

            dfs();

            if(flag) break;

        }

        if(col == )

            printf("%d channel needed.\n", col);

        else

            printf("%d channels needed.\n", col);

    }

    return ;

}