Teaching Kids Programming – Minimum Starting Nodes to Visit Graph (Topological Sort, Indegree)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional list of integers edges representing a connected, directed, acyclic graph. Each element in edges contains [u, v] meaning there is an edge from u to v. Return the minimum list of nodes from which we can visit every node in the graph, sorted in ascending order.

Constraints
0 ≤ n ≤ 100,000 where n is the length of edges

Topological Sort (Graph)

Minimum Starting Nodes to Visit Graph (Topological Sort, Indegree)

We can iterate over the edges and update the indegree for each vertex. The indegree is the number of edges that point to a vertex while the outdegree is the number of edges that go out from a vertex.

Then, we can iterate over all vertices and store the answer as those whose indegree is zero.

1
2
3
4
5
6
7
8
9
10
11
12
13

class Solution:
    def solve(self, edges):
        G = defaultdict(int)
        nodes = set()
        for u, v in edges:
            G[v] += 1
            nodes.add(u)
            nodes.add(v)
        ans = []
        for i in nodes:
            if G[i] == 0:
                ans.append(i)
        return ans

class Solution:
    def solve(self, edges):
        G = defaultdict(int)
        nodes = set()
        for u, v in edges:
            G[v] += 1
            nodes.add(u)
            nodes.add(v)
        ans = []
        for i in nodes:
            if G[i] == 0:
                ans.append(i)
        return ans

This is the fundamental of a Topological Sorting on a Graph. Time and space complexity is O(N+M) where N is the number of edges and M is the number of vertices in the given Graph.

–EOF (The Ultimate Computing & Technology Blog) —