Is the given Graph a tree? Faster than below approach --CodePudding

I was given a question during an interview and although my answer was accepted at the end they wanted a faster approach and I went blank..

Question :

Given an undirected graph, can you see if it's a tree? If so, return true and false otherwise.

A tree:

    A - B
        |
        C - D

not a tree:

     A
    / \
   B - C
  /
 D

You'll be given two parameters: n for number of nodes, and a multidimensional array of edges like such: [[1, 2], [2, 3]], each pair representing the vertices connected by the edge.

Note:Expected space complexity : O(|V|) The array edges can be empty

Here is My code: 105ms

def is_graph_tree(n, edges):
  nodes = [None] * (n   1)

 for i in range(1, n 1):
 
 nodes[i] = i

 for i in range(len(edges)):
     start_edge = edges[i][0]
     dest_edge = edges[i][1]

    if nodes[start_edge] != start_edge:
     start_edge = nodes[start_edge]

    if nodes[dest_edge] != dest_edge:
     dest_edge = nodes[dest_edge]

    if start_edge == dest_edge:
      return False

    nodes[start_edge] = dest_edge

return len(edges) <= n - 1

CodePudding user response：

You don't even need to know how many edges there are:

def is_graph_tree(n, edges):
    seen = set()
    for a,b in edges:
        b = max(a,b)
        if b in seen:
            return False
        seen.add(b)
    return True

a = [[1,2],[2,3],[3,4]]
print(is_graph_tree(0,a))
b = [[1,2],[1,3],[2,3],[2,4]]
print(is_graph_tree(0,b))

Now, this WON'T catch the case of disconnected subtrees, but that wasn't in the problem description...

CodePudding user response：

Tim Roberts has posted a candidate solution, but this will work in the case of disconnected subtrees:

import queue

def is_graph_tree(n, edges):
    # Construct graph.
    graph = [[] for _ in range(n)]
    
    for first_vertex, second_vertex in edges:
        graph[first_vertex].append(second_vertex)
        graph[second_vertex].append(first_vertex)
    
    # BFS to find edges that create cycles.
    # The graph is undirected, so we can root the tree wherever we want.
    visited = set()
    q = queue.Queue()
    q.put((0, None))
    
    while not q.empty():
        current_node, previous_node = q.get()
        if current_node in visited:
            return False
        
        visited.add(current_node)
        for neighbor in graph[current_node]:
            if neighbor != previous_node:
                q.put((neighbor, current_node))
    
    # Only return true if the graph has only one connected component.
    return len(visited) == n

This runs in O(n len(edges)) time.