11.13 联测

A

相当于每次合并两个点，两点的入边，出边，自环都要合并。

$Ans < n$，因为可以把整个图删剩一个自环。下面不妨设过程中不出现自环。

画出邻接矩阵 $G$，设某行的向量为 $r_i$，列为 $c_i$。

不难发现合并等价于 $r_y \larr r_x|r_y , c_y \larr c_x|c_y$，然后删除第 $x$ 行，第 $x$ 列。

要求最后的矩形 $G'$ 每行每列恰好一个 $1$。（我也不知道这玩意叫啥）

对于每一行的每个 $1$，把他们所在的行号用并查集并起来，列同理。

最后肯定会剩下若干个环，链。按刚刚的方法把所有连通块合并。

• 如果最后剩一个环，$ans=n-len$。
• 如果最后剩一个链，$ans=n-len-1$。