题目重点：用边预算与连通分量证明c−1，并说明重接操作、重复边和不可行条件。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 题目明确并查集求all connected需要移动几条边；没有正式移动限制，本文采用无向网络标准重接合同：一次移除已有边并把它接到任意两个节点。
- n≥1，节点0..n−1，每条边是一份可移动资源，重复边/自环也可重接；不新增资源。实际原题如限制端点、不能断开原分量或只移动单端须重新核。
- 不可行返回−1，是训练输出政策；原题未给正式规模和返回合同。
解题路线
- 先求连通分量c。每条跨分量新增连接最多让c减1，所以至少需要c−1次移动。这是下界，但还要证明有这么多不破坏原连接的边可借。
- 每个分量保留一棵生成树，全部生成森林用n−c条边，其余m−(n−c)是可挪用冗余资源。若≥c−1即可把分量连成链或星形；条件等价m≥n−1。移动生成森林外的边不会拆开原分量，达到下界。
- DSU一边扫描一边union，有效union减少c；同root的边是冗余，包括自环与平行重复。union by size加path compression避免长链。只求次数不需保存具体冗余边，如果要构造操作方案才保留edge ID和每个分量代表。
- m<n−1时，任何无向连通图至少需n−1条非自环有效连接，重接不能增加资源数，故无解。n=1按零次已连通，不能因为没有边错误判−1。
- 如果题目不允许拿自环/平行边、某些边锁定不可移动、移动费用不同或只接指定邻点，简单m判据不再充分。论文/标准题名不能替题目缺失的操作规则，文章仅声明标准训练合同。
- 独立参考枚举n≤4全部简单图，用真实“移一条边到另一个位置”的状态图反向BFS找最少操作，而非用同一分量公式作为期望；75图与2自环/平行资源样例通过。
手动走一遍
n=4，边(0,1),(1,2),(2,0)，分量{0,1,2}/{3}，三角环中一边可移到(2,3)，1次。只有(0,1),(1,2)时边数2<3，没有足够连接资源，−1。n=4有3份(0,1)平行边时，保留一份，将另两份连到2、3，2次。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
def minimum_relocations(n, edges):
"""Keep edge count; one operation removes an edge and reconnects it anywhere."""
if type(n) is not int or n < 1:
raise ValueError('positive vertex count required')
parent = list(range(n))
sizes = [1] * n
count = n
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
edge_count = 0
for u,v in edges:
if type(u) is not int or type(v) is not int or not (0 <= u < n and 0 <= v < n):
raise ValueError('vertex outside range')
edge_count += 1
a,b = find(u),find(v)
if a != b:
if sizes[a] < sizes[b]:
a,b = b,a
parent[b] = a
sizes[a] += sizes[b]
count -= 1
return count-1 if edge_count >= n-1 else -1
复杂度
O((n+m)α(n))时间、O(n)DSU工作空间；输入可流式扫描不必保存m边。构造重接清单额外O(m+n)边/代表存储；α是逆Ackermann函数，不直接把所有union find一律宣称常数。
易错点与追问
容易失分的边界
- 只数分量没查边资源。
- 每个同root边丢弃后无法构造操作。
- 自环不算原资源却套m判据。
- 有向图套无向生成森林。
- n=1判无解。
继续深挖
- 要输出每次移哪条边怎样保存edgeID？
- 边不可移动时判据如何变？
- 有向强连通为何不是c−1？
- 加权移动最小成本怎么扩展？
