Trying to use topological sort algorithm to determine if a tree is a valid

Question

You have a graph of n nodes labeled from 0 to n - 1. You are given an integer n and a list of edges where edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the graph.

Return true if the edges of the given graph make up a valid tree, and false otherwise.

enter image description here

I've used the topological sort before and essentially I try to print out the topological ordering of the graph and determine if there is a cycle. In the second example there is a cycle, yet, I'm still able to print it in topological order(see below):

class Solution:
    def validTree(self, n: int, edges: List[List[int]]) -> bool:
        indegree = [0]*(n)
        
        graph = {i:[] for i in range(n)}
        
        for child,parent in edges:
            indegree[child]+=1
            graph[parent].append(child)
            
        
        q = deque([])
        
        for i in range(len(indegree)):
            if indegree[i] == 0:
                q.append(i)
                
        top_order = []

        while q:
            node = q.popleft()
            top_order.append(node)
            for child in graph[node]:
                indegree[child]-=1
                if indegree[child]==0:
                    q.append(child)
        print(top_order)    
        return len(top_order)==n

Test Case: n = 5, edges = [[0,1],[0,2],[0,3],[1,4],[1,3]]

Result: top_order = [2, 3, 4, 1, 0] (returning true, but i'm expecting false)

Answer 1

If you simulate linking children to their parents, every child will only have one parent so there will be one edge for each child and there will be exactly one node (the root) that is not a child.

def validTree(edges):
    edges = {(a,b) for a,b in map(sorted,edges)} # make it a directed graph
    nodes = set.union(*map(set,edges))           # all nodes 
    children = {child for _,child in edges}      # distinct children
    return len(children)==len(edges) and len(nodes-children) == 1

Note: the conversion to a directed graph eliminates mirror edges but also ensure a consistent parent-child ordering within the edges. This parent-child ordering allows the final condition to cover node cycling because any cycle would either leave out a orphan child or require more edges than distinct children.

output:

validTree([[0,1],[0,2],[0,3],[1,4],[1,3]]) # False (multi-parent child)

validTree([[0,1],[0,2],[0,3],[1,4],[1,5]]) # True

validTree([[0,1],[1,2],[2,3],[4,5],[5,6],[6,7],[7,5]]) # False (cycling)

[DELETED] because this is based on an incorrect assumption that children nodes have a larger Id that their parent's, which is not necessarily the case.