0261-graph-valid-tree¶

from collections import defaultdict, deque


class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
            # top sort wont work in undiorected graph because concept of incomng graph doesn't exist here
        # we chose adjmatrix only if edges >> vertices
        return self.unionfind(n, edges)

    """
    Dfs 
     create adjacency list genarlly but choose adjacency matrix when we know edges is much larger than indices
     # 
     # via undirected  dfs to check whether a graph is acyclical
     #   we can use parent lookup 
     #        with parent lookup we can concule if neighbour is parent of node then is cyclcial
     #        skip if neighbour is the parent of node
     #        if neighbour is already seen cyclical
     #       we 
    # Time Complexity : O(N+E).
    # Space Complexity : O(N+E).
    #
    """
    def Iterativedfs(self, n: int, edges: List[List[int]]) -> bool:

        if len(edges) != n-1:
            return False
        
        adjList = defaultdict(list)

        for a, b in edges:
            adjList[a].append(b)
            adjList[b].append(a)
        
        stack = [0]
        parent = {0: -1}

        while stack:
            node = stack.pop()

            for neighbour in adjList[node]:
                if neighbour == parent[node]:
                    continue
                if neighbour in parent:
                    return False
                stack.append(neighbour)
                parent[neighbour] = node

        return len(parent) == n

    def  recursiveedfs(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n-1:
            return False
        
        adjList = defaultdict(list)

        for a, b in edges:
            adjList[a].append(b)
            adjList[b].append(a)
        
        
        seen = set()
        def dfs(node, parent):
            if node in seen:
                return
            seen.add(node)
            for neighbour in adjList[node]:
                if neighbour ==  parent:
                    continue
                if neighbour in seen:
                    return False
                if not dfs(neighbour, node):
                    return False
            return True

        
        return dfs(0, -1) and len(seen) == n

    def Iterativebfs(self, n: int, edges: List[List[int]]) -> bool:

        if len(edges) != n - 1:
            return False
        
        adjList = defaultdict(list)
        parent = {0: -1}

        for a,b in edges:
            adjList[a].append(b)
            adjList[b].append(a)
        
        queue = deque([0])

        while queue:
            node = queue.popleft()

            for neighbour in adjList[node]:
                if neighbour == parent[node]:
                    continue
                if neighbour in parent:
                    return False
                queue.append(neighbour)
                parent[neighbour] = node

        return len(parent) == n

  # Time complexity: O(n) since for E > N we return False other case E <= N hence O(E+N) = O(N)
  # Space Complexity:O(n)
    def IterativedfsAdvanced(self, n: int, edges: List[List[int]]) -> bool:
        if len(edges) != n-1:
            return False
        
        adjList = defaultdict(list)
        for a,b in edges:
            adjList[a].append(b)
            adjList[b].append(a)
        seen = set()

        def dfs(node):
            if node in seen:
                return 
            seen.add(node)
            for neighbour in adjList[node]:
                dfs(neighbour)
        dfs(0)
        return len(seen) == n 

    def unionfind(self, n: int, edges: List[List[int]]) -> bool: # [[0,1],[2,3],[4,5],[3,4],[2,5]]
        if len(edges) != n-1:
            return False

        unionFind = OptimisedUnionFind(n) # parent = [0 1 2 3 4 5 6 ]
                                          # size =   [ 1 1 1 1 1 1 1] 
        for a,b in edges: # 0 1
            if not unionFind.union(a,b): # 
                return False 
        return True
        


    #[[0,1],[0,2],[0,3],[1,4]] n = 5 
    # dryrun
    # adjList = {}
    # adjList = {0: [1, 2, 3], 1: [0] , 2:[0], 3:[0]}



class SimpleUnionFind:
    def __init__(self,n ):
        self.parent = [*range(n)]

    def find(self, A):
        while A != self.parent[A]:
            A = self.parent[A]
        return A

    def union(self, A, B):
        root_A = self.find(A)
        root_B = self.find(B)

        if root_A == root_B:
            return False
        self.parent[root_A] = root_B
        return True

class OptimisedUnionFind:
    def __init__(self,n ):
        self.parent = [*range(n)]
        self.size = [1] * n

    def find(self, A):
        root = A
        while root != self.parent[root]:
            root = self.parent[root]
        
        while A != root:
            old_root = self.parent[A]
            self.parent[A] = root
            A = old_root
        return root

    def union(self, A, B): # 2 , 3
        root_A = self.find(A) # root_A = 2
        root_B = self.find(B) # root_B = 3

        if root_A == root_B:
            return False
        
        if self.size[root_A] < self.size[root_B]: # 1 < 1
            self.parent[root_A] = root_B
            self.size[root_B] += self.size[root_A]
        else:
            self.parent[root_B] = root_A  # parent = [0 0 2 3 4 5 6 ]
            self.size[root_A] += self.size[root_B] # size =   [ 2 1 1 1 1 1 1] 
        return True