题意分析

本题主要解决广播电台中继器网络中，为避免相邻中继器信号干扰，确定最少所需频道数量的问题。输入包含多个中继器网络描述，每个网络先给出中继器数量\(N\)（\(1\leq N\leq26\)），中继器以大写字母顺序命名，当\(N = 0\)时输入结束。后续\(N\)行描述每个中继器及其相邻中继器，邻接关系对称且网络为平面图，中继器按字母序排列。输出要求针对每个有效网络，输出保证相邻中继器频道不同的最少频道数，并根据数量使用正确的单复数形式。

解题思路

1. 数据初始化：使用CLR(color,0)将存储中继器分配频道的数组color清零，同时清空每个中继器对应的相邻中继器列表vv[i] ，为后续处理做准备。
2. 构建邻接关系：遍历每个中继器，根据输入的相邻中继器信息，将相邻中继器的编号添加到对应中继器的邻接列表vv[x]中，从而构建出整个中继器网络的邻接关系图。
3. 深度优先搜索与染色判断：
   • 采用深度优先搜索（DFS）的方式，尝试给每个中继器分配不同的频道。从第一个中继器开始，依次尝试为其分配\(1\)到\(num\)（中继器总数）个不同的频道编号。
   • 在分配频道时，通过isok函数检查当前中继器与相邻中继器的频道是否冲突。isok函数遍历当前中继器的所有相邻中继器，判断是否存在与当前中继器频道相同的情况，若存在则返回false，表示当前分配方案不可行。
   • 如果当前分配的频道不冲突，则继续递归处理下一个中继器；若所有中继器都成功分配且不冲突，则说明找到了一种可行的频道分配方案，返回true。
4. 确定最少频道数：从\(1\)个频道开始，逐步增加频道数量进行尝试。一旦在某个频道数量下找到可行的分配方案，该频道数量即为满足条件的最少频道数，按要求格式输出结果。

复杂度分析

1. 时间复杂度：
   • 构建邻接关系部分，对于每个中继器，处理其相邻中继器信息的时间复杂度为\(O(m)\)（\(m\)为所有中继器相邻关系的总数），总体时间复杂度为\(O(N\times m)\) 。
   • 深度优先搜索部分，在最复杂情况下，每个中继器都尝试\(N\)个不同频道，时间复杂度为\(O(N^N)\) 。但实际由于网络的平面图性质及约束条件，平均时间复杂度远低于此值。
   • 总体时间复杂度主要取决于深度优先搜索部分，为\(O(N^N)\) 。
2. 空间复杂度：
   • 存储中继器频道分配的数组color大小为\(N\)，空间复杂度为\(O(N)\) 。
   • 存储邻接关系的vector数组vv，最坏情况下每个中继器都与其他\(N - 1\)个中继器相邻，空间复杂度为\(O(N^2)\) 。
   • 总体空间复杂度为\(O(N^2)\)。

代码实现

#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <queue>
#include <string>
using namespace std;

#define CLR(arr,val) memset(arr,val,sizeof(arr))
const int N = 30;
int color[N],num;
vector<int> vv[N];

// 检查当前中继器x的频道分配是否与相邻中继器冲突
bool isok(int x){
    for(int i = 0; i < vv[x].size(); ++i){
        int y = vv[x][i];
        if(color[x] == color[y]) return false;
    }
    return true;
}

// 深度优先搜索函数，尝试为中继器分配频道
bool dfs(int cnt,int numcolor){
    if(cnt > num) return true; // 所有中继器都成功分配频道，返回true
    else{
        for(int i = 1; i <= numcolor; ++i){
            color[cnt] = i;
            if(isok(cnt)){ // 当前分配的频道不冲突
                if(dfs(cnt+1,numcolor)) // 继续为下一个中继器分配频道
                    return true;
            }
            color[cnt] = 0; // 回溯，撤销当前分配
        }
    }
    return false;
}

int main(){
    //freopen("1.txt","r",stdin);
    while(scanf("%d",&num) &&num){
        CLR(color,0);
        string ss;
        for(int i = 1;i <= num; ++i)
            vv[i].clear();
        // 构建邻接关系
        for(int i = 1; i <= num; ++i){
            cin >> ss;
            if(ss.size() <= 2)
                continue;
            int x = (int)(ss[0] - 'A' + 1);
            for(int j = 2; j < ss.size(); ++j){
                int y = (int)(ss[j] - 'A' + 1);
                vv[x].push_back(y);
            }
        }
        // 尝试不同频道数量，找到最少所需频道数
        for(int i = 1; i <= num; ++i){
            if(dfs(1,i)){
                if(i == 1){
                    printf("1 channel needed.\n");
                }
                else
                    printf("%d channels needed.\n",i);
                break;
            }
        }
    }
    return 0;
}

✅ 解题步骤：

构建邻接图：

使用邻接表或邻接矩阵存储每个中继器之间的邻接关系；

字母 A～Z 可映射为索引 $0$～$25$。

尝试染色：

从颜色数 $1$ 开始尝试；

用回溯尝试每个中继器是否能在 $k$ 种颜色下合法染色；

一旦找到满足条件的最小 $k$，即为答案。

输出结果：

输出格式根据 $k$ 是 $1$ 还是其他确定单复数。

🧮 时间复杂度分析

$N \leq 26$，搜索树最大为 $k^N$；

实际中剪枝非常有效，尤其配合邻接排序优化染色顺序；

可在合理时间内得到结果。

💡 举个例子说明染色：

对于如下输入：

makefile 复制 编辑 A:BC B:ACD C:ABD D:BC 图结构如下：

less 复制 编辑 A——B——D | | C——— A 与 B、C 相邻；

B 与 A、C、D 相邻；

C 与 A、B、D 相邻；

D 与 B、C 相邻；

这是一个包含三角形和四边形的结构，最小染色数为 $3$。

代码实现：

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <string>
#include <set>
#include<vector>
#include <map>
using namespace std;
#define inf 0x3f3f3f3f

int mp[30][30];
int a[30];
int ok,mx;

void dfs(int p)
{
    if(p>=26)
    {
        ok=1;
        return ;
    }
    for(int i=1; i<=4; i++)
    {
        mx=max(mx,i);
        int flag=0;
        for(int j=0; j<26; j++)
            if(mp[p][j]==1&&a[j]==i)
            {
                flag=1;
                break;
            }
        if(flag==0)
            a[p]=i,dfs(p+1);
        if(ok) return;
    }
}
int main()
{
    int n;
    char s[1000];
    while(~scanf("%d",&n)&&n)
    {
        memset(mp,0,sizeof mp);
        memset(a,0,sizeof a);
        for(int i=0; i<n; i++)
        {
            scanf("%s",&s);
            int k=strlen(s);
            for(int j=2; j<k; j++)
            {
                mp[s[0]-'A'][s[j]-'A']=1;
            }
        }
        ok=0;
        mx=-1;
        dfs(0);
        printf("%d channel%s needed.\n",mx,mx>1?"s":"");
    }
    return 0;
}