核心思想

哈希等价类划分：将具有完全相同联系人集合的居民归为同一城市。

重要公式

1. 随机标识生成

为每个居民 $i$ 生成唯一随机值：

$$val[i] = \text{random64}()$$

2. 联系人集合哈希

对居民 $i$，计算其联系人集合的哈希签名：

$$g[i] = val[i] \oplus \left( \bigoplus_{x \in \text{contacts}[i]} val[x] \right) $$

3. 城市划分条件

两个居民 $i,j$ 属于同一城市当且仅当：

$$g[i] = g[j]$$

4. 城市连接条件

城市 $u$ 与城市 $v$ 相连当且仅当存在居民 $i \in u$ 和居民 $j \in v$ 使得：

$$j \in \text{contacts}[i] \quad \text{且} \quad i \in \text{contacts}[j] $$

算法正确性保证

• 同城居民：联系人集合完全相同 → 哈希值相同
• 相邻城市居民：联系人集合不同但互相关联 → 哈希值不同但存在边连接
• 不相邻城市居民：无直接联系 → 哈希值不同且无边连接

特殊情况处理

当 $n > 1$ 且 $m = 1$ 时，说明所有居民的联系人集合相同，此时必须至少划分为两个城市：

$$m = \max(m, 2)$$