本文主要是介绍LeetCode - 1319. 连通网络的操作次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
描述
用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
示例 1：
输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2
示例 3：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。
示例 4：
输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0
提示：
1 <= n <= 10^5
1 <= connections.length <= min(n*(n-1)/2, 10^5)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/number-of-operations-to-make-network-connected/
求解
class Solution {public:// 方法一，图深度优先搜索获取连通分量int makeConnected_1e(int n, vector<vector<int>> &connections) {if (connections.size() < n - 1) {// n个节点的图最小生成树是n-1条边，如果边少于n-1，肯定无法进行全部节点的连通return -1;}// 构造图，采用邻接表存储vector<vector<int>> graph(n, vector<int>());for (const auto &edge : connections) {graph[edge[0]].emplace_back(edge[1]);graph[edge[1]].emplace_back(edge[0]);}// 深度优先遍历visited.assign(n, false);int count = 0; // 连通分量for (int i = 0; i < n; ++i) {if (!visited[i]) {++count;dfs(graph, i);}}return count - 1;}// 方法二，图广度优先搜索获取连通分量int makeConnected_2e(int n, vector<vector<int>> &connections) {if (connections.size() < n - 1) {// n个节点的图最小生成树是n-1条边，如果边少于n-1，肯定无法进行全部节点的连通return -1;}// 构造图，采用邻接表存储vector<vector<int>> graph(n, vector<int>());for (const auto &edge : connections) {graph[edge[0]].emplace_back(edge[1]);graph[edge[1]].emplace_back(edge[0]);}// 广度优先遍历visited.assign(n, false);int count = 0; // 连通分量queue<int> q;for (int i = 0; i < n; ++i) {if (!visited[i]) {++count;q.emplace(i);visited[i] = true; // 将顶点加入队列后，需要立马将其标志位置位已访问状态，因为后序肯定会访问到该顶点，避免多次加入相同顶点while (!q.empty()) {int v = q.front();q.pop();for (const auto &w : graph[v]) {if (!visited[w]) {q.emplace(w);visited[w] = true; // 将顶点加入队列后，需要立马将其标志位置位已访问状态}}}}}return count - 1;}// 方法三，并查集，速度最快，使用内存最少int makeConnected(int n, vector<vector<int>> &connections) {if (connections.size() < n - 1) {// n个节点的图最小生成树是n-1条边，如果边少于n-1，肯定无法进行全部节点的连通return -1;}// 并查集数据初始化rank.assign(n, 0);parent.assign(n, 0);for (int i = 0; i < n; ++i) {parent[i] = i;}// 根据边进行顶点关联for (const auto &edge : connections) {unionElements(edge[0], edge[1]);}return getConCount() - 1;}private:vector<bool> visited; // 图节点的访问标志vector<int> parent; // 并查集数据结构vector<int> rank; // 并查集层级记录，用于优化// 并查集查找函数int find(int p) {while (p != parent[p]) {parent[p] = parent[parent[p]];p = parent[p];}return p;}// 并查集关联函数void unionElements(int p, int q) {int pid = find(p);int qid = find(q);if (pid != qid) {if (rank[pid] < rank[qid]) {parent[pid] = qid;return;}if (rank[pid] > rank[qid]) {parent[qid] = pid;return;}// rank[pid] == rank[qid]parent[pid] = parent[qid];++rank[qid];}}// 并查集计算连通分量函数int getConCount() {int count = 0;for (int i = 0; i < parent.size(); ++i) {if (i == parent[i]) {++count;}}return count;}// 图的深度优先搜索void dfs(const vector<vector<int>> &graph, int v) {visited[v] = true;for (auto w : graph[v]) {if (!visited[w]) {dfs(graph, w);}}}};
这篇关于LeetCode - 1319. 连通网络的操作次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
