LeetCode-Python-261. 図で木を判断する

0からn-1の符号のn個のノードと、無方向エッジリスト(各エッジはノードペアで表される)を指定し、これらのエッジが合法的で有効なツリー構造を形成できるかどうかを判断する関数を作成します.
例1:
入力:n=5、エッジリストedges=[[0,1],[0,2],[0,3],[1,4]]出力:true例2:
入力:n=5、エッジリストedges=[[0,1],[1,2],[2,3],[1,3],[1,4]]出力:false注意:エッジリストedgesに重複するエッジが現れないと仮定できます.すべてのエッジが無方向エッジであるため、エッジ[0,1]とエッジ[1,0]は同じであるため、エッジリストedgesには同時に現れない.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/graph-valid-tree著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
まず、ツリーの定義を理解します.
私の個人的な理解は簡単に言えば、1つの図は、図の中のあるノードから出発して、すべてのノードに着くことができて、しかも図の中にリングがなければ、この図は木と呼ぶことができます.
だからこの問題について、私たちは2つのものを判断する必要があります.
1.ルートノードが1つしかないか(何人かのギャングのボスを探すのと同じ)
2.図にリングがあるかどうか
 
最初の問題は非常に典型的な並列調査セット応用であるため,本題は並列調査セットで問題を解く.
開いてセットを調べ、すべてのエッジを捨ててセットを調べる前に、ボスが違うと判断してください.
同じようになったら、投げ込んでからリングが形成されると説明します.
図にリングが存在しない場合は,最後にいくつかのノードがあると判断すればよい.

class UnionFindSet(object):
    def __init__(self, n):
        self.count = n
        self.roots = [i for i in range(n)]
        
    def find(self, node):
        while self.roots[node] != node:
            node = self.roots[node]
        return node
    
    def union(self, p, q):
        p_parent = self.find(p)
        q_parent = self.find(q)
        self.roots[p_parent] = q_parent
        self.count -= 1
        
class Solution(object):
    def validTree(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: bool
        """
        #    ，                        ，                 
        ufs = UnionFindSet(n)
        for start, end in edges:
            if ufs.find(start) == ufs.find(end):
                return False
            ufs.union(start, end)
        # print ufs.count
        return ufs.count == 1