Description
Since the radio frequency spectrum is a precious resource, the number of channels required by a given network of repeaters should be minimised. You have to write a program that reads in a description of a repeater network and determines the minimum number of channels required.
Input
Following the number of repeaters is a list of adjacency relationships. Each line has the form:
A:BCDH
which indicates that the repeaters B, C, D and H are adjacent to the repeater A. The first line describes those adjacent to repeater A, the second those adjacent to B, and so on for all of the repeaters. If a repeater is not adjacent to any other, its line has the form
A:
The repeaters are listed in alphabetical order.
Note that the adjacency is a symmetric relationship; if A is adjacent to B, then B is necessarily adjacent to A. Also, since the repeaters lie in a plane, the graph formed by connecting adjacent repeaters does not have any line segments that cross.
Output
Sample Input
2
A:
B:
4
A:BC
B:ACD
C:ABD
D:BC
4
A:BCD
B:ACD
C:ABD
D:ABC
0
Sample Output
1 channel needed.
3 channels needed.
4 channels needed.
【题意】给出n个点，再给出n个点各自相邻的点，相邻的点不能是一个颜色，问至少需要几个颜色；
【思路】
对点i的染色操作：从最小的颜色开始搜索，当i的直接相邻（直接后继）结点已经染过该种颜色时，搜索下一种颜色。
就是说i的染色，当且仅当i的临近结点都没有染过该种颜色，且该种颜色要尽可能小。
参考：http://www.cnblogs.com/lyy289065406/archive/2011/07/31/2122590.html
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
typedef class
{
public:
int next[];
int num;
}point;
int main()
{
int n;
while(~scanf("%d",&n),n)
{
getchar();//回车
point* a=new point[n+];
for(int i=;i<=n;i++)
{
getchar();//当前的点
getchar();//冒号
if(a[i].num<)
{
a[i].num=;//初始化
}
char ch;
while((ch=getchar())!='\n')
{
int tmp=ch%('A'-);//与当前的点相邻的点A->1,B->2...
a[i].next[++a[i].num]=tmp;//存入a[i]的next数组中
}
}
int color[];
memset(color,,sizeof(color));
color[]=;//第一点一定需要一种颜色
int maxcolor=;//至少需要一种颜色
for(int i=;i<=n;i++)
{
color[i]=n+;//先把第i个点的颜色置为最大
int vis[];
memset(vis,false,sizeof(vis));
for(int j=;j<=a[i].num;j++)
{
int k=a[i].next[j];//第i个点的第j个相邻的点
if(color[k]) vis[color[k]]=true;//如果他已经有颜色的话，就把那种颜色标记为true；
}
for(int j=;i<=n;j++)
{
if(!vis[j]&&color[i]>j)//如果j种颜色没用过，并且小于color[i]就把color[i]赋值为j；
{
color[i]=j;
break;
}
}
for(int i=;i<=n;i++)
{
if(maxcolor<color[i])
{
maxcolor=color[i]; }
if(maxcolor==) break;//最大的颜色不超过四种，根据四色定理
} } if(maxcolor==)
printf("1 channel needed.\n");
else printf("%d channels needed.\n",maxcolor);
delete a;
} return ;
}