1319. Number of Operations to Make Network Connected

题目信息

题号:

1319

难度:

Medium

主题:

图、并查集、连通分量

原题:

LeetCode 1319

重点:

可拔下一条已有网线并连接任意两台未直连计算机;至少需要 n-1 条网线,答案为连通分量数减一

题目重述

有 n 台计算机,connections[i] = [a,b] 表示两台计算机之间有一条网线。一次操作可以移除任意一条现有网线,再用它连接任意两台计算机。

请返回使整个网络连通所需的最少操作数。若现有网线总数不足以连接所有计算机,返回 -1。

1 <= n <= 10^5,连接数不超过 10^5,每条连接的两个端点不同且无重复边。

自建示例

冗余环路网线可以连接两个分量:

输入:n = 5, connections = [[0,1],[1,2],[2,0],[3,4]]
输出:1
解释:前三台形成环,可移除其中一条冗余网线并连接两个连通分量。

网线数量不足时无解:

输入:n = 4, connections = [[0,1],[2,3]]
输出:-1
解释:连接四台计算机至少需要三条网线,但当前只有两条。