Leetcode 261. Graph Valid Tree(python)

Leetcode 261. Graph Valid Tree

題

解法1:DFS

解法2:BFS

解法3:並列調査セット

参照リンク:

タイトル
Given n nodes labeled from 0 to n-1 and a list of undirected edges (each edge is a pair of nodes), write a function to check whether these edges make up a valid tree. Example 1: Input: n = 5, and edges = [[0,1], [0,2], [0,3], [1,4]] Output: true Example 2: Input: n = 5, and edges = [[0,1], [1,2], [2,3], [1,3], [1,4]] Output: false
解法1:DFS
edges構成エッジは2つの条件を満たす必要があります.

全ての辺が連通図

を構成する.

すべてのエッジがループにならないこちらは無方向図のループ検出であり、有方向図の変換検出は207を参照する.Course Scheduleが連通図を構成するかどうかの判断:visited配列を構築し、配列長はノード数と同じであり、連通図を構成する必要条件は、この配列の各要素がアクセスループによって検出される:visitedにすでにある要素にアクセスすることがループである.ただし,ここではdictを構築する際に双方向であるため,現在のノードのparentノードを判断する必要がある.

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:        
        if len(edges) != n-1:
            return False
        memo = collections.defaultdict(list)
        for edge in edges:
            memo[edge[0]].append(edge[1])
            memo[edge[1]].append(edge[0])
        visited = [False]*n
        def helper(curr,parent):
            if visited[curr]:
                return False
            visited[curr] = True
            for val in memo[curr]:
                if val!= parent and not helper(val,curr):
                    return False
            return True
        if not helper(0,-1):
            return False
        for v in visited:
            if not v:
                return False
        return True

解法2:BFS
BFSの判定条件は,すべてのpairがアクセスされた後,アクセスされたノード数がnと同じである.

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:        
        if len(edges) != n - 1:  # Check number of edges.
            return False
 
        # init node's neighbors in dict
        neighbors = collections.defaultdict(list)
        for u, v in edges:
            neighbors[u].append(v)
            neighbors[v].append(u)
 
        # BFS to check whether the graph is valid tree.
        visited = {}
        q = collections.deque([0])
        while q:
            curr = q.popleft()
            visited[curr] = True
            for node in neighbors[curr]:
                if node not in visited:
                    visited[node] = True
                    q.append(node)
 
        return len(visited)==n

解法3:集計(union find)
後続の補充を保留する
参照リンク:
https://www.cnblogs.com/lightwindy/p/8636516.html