In graph theory, a graph is a collection of nodes with connections between them.
Any node can be connected to any other node exactly once, and can be connected to no nodes, to some nodes, or to every other node.
Nodes cannot be connected to themselves
A path through a graph is a sequence of nodes, with every node connected to the node following and preceding it.
A closed path is a path which starts and ends at the same node.

An open path:
```
1 -> 2 -> 3
```
a closed path:
```
1 -> 2 -> 3 -> 1
```
A graph is connected if there is a path from every node to every other node.
A graph is a tree if it is connected and there are no closed paths.


Your job is to write a function 'isTree', which returns true if a graph is a tree, and false if it is not a tree.

Graphs will be given as an array with each item being an array of integers which are the nodes that node is connected to.

For example, this graph:
```
0--1
|  |
2--3--4
```
has array:
```
[[1,2], [0,3], [0,3], [1,2,4], [3]]
```
Note that it is also not a tree, because it contains closed path:
```
0->1->3->2->0
```
A node with no connections is an empty array
Note that if node 0 is connected to node 1, node 1 is also connected to node 0. This will always be true.
The order in which each connection is listed for each node also does not matter.

Good luck!

Difficulty: introductory

Starter code:

def isTree(matrix):
	

Solutions:
def isTree(matrix):
    visited_nodes = set([0])
    crossed_edges = set()
    agenda = [0]

    while agenda:
        node = agenda.pop()
        for i in matrix[node]:
            if (node, i) in crossed_edges: continue 
            if i in visited_nodes: return False
            agenda.append(i)
            crossed_edges.add( (i, node) )
            visited_nodes.add(i)
    
    return len(visited_nodes) == len(matrix)

def isTree(matrix):
    seen, stack = set(), [0]
    while stack:
        node = stack.pop()
        if node in seen:
            return False
        seen.add(node)
        stack += list(set(matrix[node]) - seen)
    return len(seen) == len(matrix)

def isTree(matrix):
    visited = [False] * len(matrix)

    def traverse(origin, transit):
        if not visited[transit]:
            visited[transit] = True
            return all(traverse(transit, destination) for destination in matrix[transit] if destination != origin)
        
    return traverse(None, 0) and all(visited)

def isTree(matrix):
    '''depth first search; tree on n vertices has exactly n-1 edges'''
    vertices = set(range(len(matrix)))
    stack = [vertices.pop()]
    while stack:
        children = {y for y in matrix[stack.pop()] if y in vertices}
        vertices.difference_update(children)
        stack.extend(children)
    return not vertices and sum(map(len,matrix)) == 2 * len(matrix) - 2

def isTree(Q) :
    if not len(Q) : return False
    H = [0] * len(Q)
    U = [[-1,0]]
    while len(U) :
        F,T = U.pop()
        if H[T] : return False
        H[T] = 1
        U += [[T,V] for V in Q[T] if V != F]
    return len(Q) == sum(H)

def visit(ad_lst, i, fth=-1, path=[], visited=0):
    if i in path:
        return [], -1
    visited += 1
    path.append(i)
    for v in range(0, len(ad_lst[i])):
        if fth == ad_lst[i][v]:
            continue
        path2, v2 = visit(ad_lst, ad_lst[i][v], i, path)
        if len(path2) == 0:
            return [], -1
        path = path2
        visited += v2
    return path, visited
        
def isTree(ad_lst):
    for v in range(0, len(ad_lst)):
        path, visited = visit(ad_lst, v, -1, [], 0)
        if len(path) == 0:
            return False
        if visited == len(ad_lst):
            return True
    return False

def isTree(matrix):
    seen = [False] * len(matrix)

    def traverse(from_node, to_node):
        if not seen[to_node]:
            seen[to_node] = True
            for next_node in matrix[to_node]:
                if next_node != from_node:
                    if not traverse(to_node, next_node):
                        return False
            return True
        
    return traverse(None, 0) and all(seen)

from collections import defaultdict

def isTree(matrix):
    graph = defaultdict(set)
    for node, connections in enumerate(matrix):
        if not connections:
            return False
        for connection in connections:
            graph[connection].add(node)
            graph[node].add(connection)
            
    N = len(matrix)
    for node in graph.keys():
        stack, seen = [node], set()
        while stack:
            cur_node = stack.pop()
            if cur_node in seen:
                return False
            seen.add(cur_node)
            for next_node in graph[cur_node]:
                if next_node not in seen:
                    stack.append(next_node)
        if len(seen) < N:
            return False
    return True

def isTree(m):
    status = [(e, 0) for e in m[0]]
    seen = set([0]) if status else set()
    while status:
        t, f = status.pop()
        seen.add(t)
        for e in m[t]:
            if e != f:
                if e in seen:
                    return False
                seen.add(e)
                status.append((e, t))
    return len(seen) == len(m)

def s(m, b, e, v):
    v[b] += 1
    if v[b] > 1:
        return v
    for i in range(len(m[b])):
        if m[b][i] != e:
            v = s(m,m[b][i],b,v)
    return v

def isTree(m):
    v = [0]*len(m)
    v = s(m, 0, -1, v)
    return v == [1]*len(v)