题目大意 有 nnn 个点，mmm 条边的无向图，如果点 aaa 和点 bbb 有一条边，点 aaa 和点 ccc 有一条边，而点 bbb 和点 ccc 之间没有边，则可以在点 bbb 和点 ccc 之间添加一条边，求最多可以添加多少条边。 解题思路 不难发现，在一个连通块内的所有点都可以通过若干次操作使得每两个点之间连上一条边。于是，我们求出每个连通块的大小 szszsz 和已有边数 edgsedgsedgs ，就可以求出连通块内没有连接的边数 sz×(sz−1)2−edgs\frac{sz\times(sz-1)}{2} - edgs2sz×(sz−1) −edgs，也就是答案。 可以用并查集维护 szszsz 以及 edgsedgsedgs 。 时间复杂度 O(nlogn)O(nlogn)O(nlogn) 参考代码