Graph Valid Tree

Problem Id: 261 Difficulty: Medium


Intuition

Prequirements of a graph to be a tree.

Solution


class Graph:
    def __init__(self, size):
        self.size = size
        self.adj = [[] for _ in range(size)]

    def add_edge(self, p, q):
        self.adj[p].append(q)
        self.adj[q].append(p)


class ConnectAndNoCycle:
    def __init__(self, graph):
        self.visited = [False] * graph.size
        self.cycle = False

        self.dfs(graph, None, 0)

        self.connected = all(self.visited)

    def dfs(self, graph, parent, vertex):
        self.visited[vertex] = True
        for child in graph.adj[vertex]:
            if self.cycle:
                break
            if not self.visited[child]:
                self.dfs(graph, vertex, child)
            elif child != parent:
                self.cycle = True


class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        graph = Graph(n)
        for p, q in edges:
            if p == q:
                return False
            graph.add_edge(p, q)
        res = ConnectAndNoCycle(graph)
        return (not res.cycle) and res.connected