问题分析

我们需要设计一个策略，使得无论米拉和劳拉：

1. 从哪两个不同的房间开始
2. 在多个合法移动选择时如何随机选择

都能在有限步内相遇（同一房间或经过同一条边）。

关键约束：

• 我们不知道她们的初始位置
• 我们不知道她们在多个同色相邻房间时的选择
• 图是连通的，$N \leq 100$
• 最多 $20000$ 次操作，目标是最小化操作次数

算法核心思想

1. 问题转化

这是一个图上的确定性问题。我们需要设计一个确定性的颜色序列，使得：

• 对于任意两个不同的起始点
• 所有可能的移动选择
• 最终都会相遇

2. 关键观察

代码采用了一种随机化构造的方法：

• 随机选择一个根节点，进行DFS建立层次结构
• 寻找一个特殊的节点 p，其所有子节点的子节点深度都大于1
• 使用交替的颜色模式引导两人移动

算法详解

数据结构

vector<int> G[MAXN];  // 邻接表
int d[MAXN];          // 深度，从根节点开始的距离
int c[MAXN];          // 所属分支
int rt, p;            // 根节点和特殊节点

算法步骤

步骤1：随机化建树

for (int _ = 0; _ < 1000; ++_) {
    // 随机打乱邻接表顺序
    for (int i = 1; i <= n; ++i)
        shuffle(G[i].begin(), G[i].end(), rnd), d[i] = c[i] = 0;
    
    // 随机选择根节点
    rt = rnd() % n + 1, d[rt] = 1, dfs(rt);
    
    if (p) break;  // 找到合适的p就停止
}

步骤2：DFS寻找特殊节点

void dfs(int u) {
    bool ok = d[u] == 2;  // 只考虑深度为2的节点
    
    for (int v : G[u]) {
        if (!d[v]) {
            d[v] = d[u] + 1;
            // 如果深度>1，继承父节点的分支；否则，用自己作为分支
            c[v] = d[u] > 1 ? c[u] : v;
            dfs(v);
            
            // 检查v的所有邻居深度是否都>1
            if (ok)
                for (int w : G[v])
                    ok &= d[w] > 1;
        }
    }
    
    if (ok) p = u;  // 找到符合条件的节点
}

p 的性质：

• 深度为2
• 所有子节点的邻居深度都大于1
• 这保证了从 p 出发的结构比较规整

步骤3：生成颜色序列

生成600轮颜色配置（题目要求≤600次操作可得满分）：

for (int t = 0; t < 600; ++t) {
    for (int i = 1; i <= n; ++i) {
        if (t & 1)  // 奇数轮
            cout << (d[i] + 1) / 2 << " \n"[i == n];
        else        // 偶数轮
            cout << d[i] / 2 + 1 - (c[i] == p) << " \n"[i == n];
    }
}

颜色分配规则

奇数轮（t为奇数）：

颜色 = $\lfloor (d[i] + 1) / 2 \rfloor$

效果：

• 深度为1的节点：颜色1
• 深度为2的节点：颜色1
• 深度为3的节点：颜色2
• 深度为4的节点：颜色2
• ...

偶数轮（t为偶数）：

颜色 = $\lfloor d[i] / 2 \rfloor + 1 - (c[i] == p)$

效果：

• 对于属于分支 p 的节点，颜色减1
• 其他节点按深度分组

算法原理

为什么这样能保证相遇？

1. 交替模式引导移动

• 奇数轮和偶数轮的颜色模式不同
• 这创造了一种"振荡"效果，使两人在图中来回移动

2. 深度分组

• 将节点按深度分组赋予相同颜色
• 这限制了移动方向：只能在同一深度组内或相邻组间移动

3. 特殊节点 p 的作用

• p 是一个深度为2的关键节点
• 在偶数轮中，属于 p 分支的节点颜色不同
• 这创造了不对称性，有助于打破对称状态

正确性保证

虽然代码没有提供严格的数学证明，但该策略基于以下原理：

1. 连通性：图是连通的，总存在路径连接任意两点
2. 周期性：600轮的交替模式足够长，覆盖所有可能情况
3. 随机化：多次随机尝试增加找到有效策略的概率

复杂度分析

• 时间：

  • 最多1000次随机尝试
  • 每次尝试DFS：$O(N + M)$
  • 生成输出：$O(600 \times N)$
  • 总复杂度可接受

• 空间：$O(N + M)$ 存储图

• 操作次数：固定600次，满足满分要求（≤600次）

示例分析

样例输入

3 2
0 1
1 2

这是一个长度为3的路径图：0-1-2

可能的执行过程：

1. 随机选择根节点（比如节点1）
2. DFS得到深度：d[1]=1, d[0]=2, d[2]=2
3. 找到特殊节点 p（假设是节点0）
4. 生成600轮颜色序列

前几轮可能如样例所示，引导两人相遇。

算法优势

1. 简单有效：代码简短，但能解决复杂问题
2. 满足约束：固定600次操作，可得满分
3. 通用性：适用于各种图结构（树、完全图、一般图）
4. 随机化增强鲁棒性：多次尝试增加成功率

局限性

1. 非确定性：依赖随机化，理论上可能失败（概率极低）
2. 缺乏理论保证：没有严格证明一定成功
3. 固定次数：总是输出600次，可能不是最优

改进方向

1. 确定性算法：设计无需随机化的策略
2. 自适应次数：根据图大小动态确定操作次数
3. 优化颜色分配：设计更高效的颜色模式

总结

这是一个巧妙的随机化构造算法，通过：

• 随机DFS建立层次结构
• 寻找关键节点创造不对称性
• 交替颜色模式引导移动

实现了无论初始位置和随机选择如何，都能保证两人相遇。虽然缺乏严格证明，但实践中效果良好，且满足题目要求（600次操作可得满分）。