题意:
N个中继站,相邻的中继站频道不得相同,问最少需要几个频道。
输入输出:
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个点的无向图,对每个点进行染色,相邻的点颜色不得一致,最少需多少种颜色。DFS即可。
代码:
int nmax;
bool mapp[30][30], is[30], coll[30];
int col[30];
void dfs(int u){
mem(coll,false);
rep(i,0,25){
if(u!=i && mapp[u][i] && col[i]){
coll[col[i]] = true;
}
}
rep(i,26,1) if(coll[i]){
nmax = i;
break;
}
rep(i,1,26) if(!coll[i]){
col[u] = i;
nmax = max(nmax,i);
break;
}
rep(i,0,25){
if(u!=i && mapp[u][i] && !col[i])
dfs(i);
}
}
int main(){
int n;
char s[100];
while(scanf("%d",&n),n){
mem(mapp,false);
mem(is,false);
mem(col,0);
while(n--){
scanf("%s",s);
int l=strlen(s);
is\[s\[0\]-'A'\] = true;
rep(i,2,l-1){
mapp\[s\[0\]-'A'\]\[s\[i\]-'A'\] = true;
mapp\[s\[i\]-'A'\]\[s\[0\]-'A'\] = true;
is\[s\[i\]-'A'\] = true;
}
}
nmax = 0;
rep(i,0,25){
if(is\[i\] && !col\[i\]) dfs(i); //对i进行染色,并从i开始把那个集合中的点都染上色
}
if(nmax==1) printf("%d channel needed.\\n",nmax);
else printf("%d channels needed.\\n",nmax);
}
}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章