poj 1129 Channel Allocation ( dfs )

题目：http://poj.org/problem?id=1129

题意：求最小m，使平面图能染成m色，相邻两块不同色
由四色定理可知顶点最多需要4种颜色即可。我们于是从1开始试到3即可。

 #include <iostream>

  #include<cstdio>

  #include<cstring>

  #include<cstdlib>

  #include<stack>

  #include<queue>

  #include<iomanip>

  #include<cmath>

  #include<map>

  #include<vector>

  #include<algorithm>

  using namespace std;

  int n,G[][],vis[][],ans;

  void pri()

  {

      int f=-;

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

      {

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

              if(vis[j][i]&&f<i)

                  f=i;

      }

      if(ans>f)

          ans=f;

  }

  void dfs(int x)

  {

      if(x>=n)

      {

          pri();

          return;

      }

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

      {

          int f=;

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

          {

              if((G[j][x]&&vis[j][i])||(G[x][j]&&vis[j][i]))

              {

                  f=;

                  break;

              }

          }

          if(f)

          {

              vis[x][i]=;

              dfs(x+);

              vis[x][i]=;

          }

      }

  }

  int main()

  {

      char s[];

      while(cin>>n&&n)

      {

          memset(G,,sizeof(G));

          memset(vis,,sizeof(vis));

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

          {

              cin>>s;

              int u=s[]-;

              for(int j=; s[j]; j++)

              {

                  int v=s[j]-;

                  G[u][v]=;

              }

          }

          ans=;

          vis[][]=;

          dfs();

          ans+=;

          if(ans == )

          printf("1 channel needed.\n");

          else

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

      }

      return ;

  }