LeetCode题解(1319)：连通网络的操作次数(Python)

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode题解(1319)：连通网络的操作次数(Python)，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1110字，纯文字阅读大概需要2分钟。

内容图文

题目：原题链接（中等）

标签：并查集、广度优先搜索、深度优先搜索

解法一：

class DSU1:
    def __init__(self, n: int):
        self._n = n
        self._array = [i for i in range(n)]
        self._size = [1] * n

    def find(self, i: int):
        if self._array[i] != i:
            self._array[i] = self.find(self._array[i])
        return self._array[i]

    def union(self, i: int, j: int):
        i, j = self.find(i), self.find(j)
        if self._size[i] >= self._size[j]:
            self._array[j] = i
            self._size[i] += self._size[j]
        else:
            self._array[i] = j
            self._size[j] += self._size[i]

    def group_num(self):
        groups = set()
        for i in range(len(self._array)):
            if self._array[i] not in groups:
                j = self.find(i)
                if j not in groups:
                    groups.add(self.find(i))
        return len(groups)

    def __repr__(self):
        return str(len(self._array)) + ":" + str(self._array)


class Solution:
    def makeConnected(self, n: int, connections: List[List[int]]) -> int:
        dsu = DSU1(n)
        surplus = 0
        for a, b in connections:
            if dsu.find(a) == dsu.find(b):
                surplus += 1
            else:
                dsu.union(a, b)

        return dsu.group_num() - 1 if dsu.group_num() - 1 <= surplus else -1

内容总结

以上是互联网集市为您收集整理的LeetCode题解(1319)：连通网络的操作次数(Python)全部内容，希望文章能够帮你解决LeetCode题解(1319)：连通网络的操作次数(Python)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端