Leetcode 1557: Minimum Number of Vertices to Reach All Nodes

Input: The input consists of the number of vertices n and an array of directed edges.

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

Constraints:

• 2 <= n <= 10^5

• 1 <= edges.length <= min(10^5, n * (n - 1) / 2)

• edges[i].length == 2

• 0 <= fromi, toi < n

• All pairs (fromi, toi) are distinct

Output: Return the smallest set of vertices from which all nodes in the graph are reachable.

Example: Output: [0, 2, 3]

Constraints:

• The output should be a list of vertices.

Goal: The goal is to find the smallest set of vertices that can reach all the nodes in the graph.

Steps:

• 1. Initialize an array to track the number of incoming edges for each vertex.

• 2. Traverse the edges to update the number of incoming edges for each vertex.

• 3. Identify vertices that have no incoming edges (i.e., vertices that must be included in the set).

• 4. Return the list of these vertices.

Goal: The solution should work efficiently for large graphs with up to 10^5 vertices and 10^5 edges.

Steps:

• The solution must handle up to 10^5 vertices and edges efficiently.

Assumptions:

• The graph is a directed acyclic graph (DAG).

• There is always a unique solution.

• Input: n = 6, edges = [[0, 1], [0, 2], [2, 5], [3, 4], [4, 2]]

• Explanation: From vertex 0, we can reach nodes [0, 1, 2, 5], and from vertex 3, we can reach nodes [3, 4, 2, 5]. Therefore, the smallest set of vertices is [0, 3].

• Input: n = 5, edges = [[0, 1], [2, 1], [3, 1], [1, 4], [2, 4]]

• Explanation: The vertices 0, 2, and 3 are not reachable from any other node, so they must be included in the set. Any of these vertices can reach nodes 1 and 4.

Approach: The approach involves identifying vertices with no incoming edges, as these must be included in the smallest set of vertices that can reach all nodes.

Observations:

• The smallest set of vertices will be those that are not reachable from other vertices.

• By counting the number of incoming edges for each vertex, we can identify those vertices that must be included in the solution.

Steps:

• 1. Create an array to store the count of incoming edges for each vertex.

• 2. Traverse the edges and update the count of incoming edges for the destination vertices.

• 3. Identify the vertices with zero incoming edges and add them to the result.

• 4. Return the list of these vertices.

Empty Inputs:

• There are no empty inputs as n >= 2.

Large Inputs:

• The solution must efficiently handle large inputs with n up to 10^5.

Special Values:

• The graph is guaranteed to have a unique solution.

Constraints:

• The graph is a directed acyclic graph (DAG).

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {
    vector<int> ca(n, 0);
    vector<int> ans;
    for(auto e: edges) {
        ca[e[1]]++;
    }
    for(int i = 0; i< n ; i++)
    if(ca[i] == 0) ans.push_back(i);
    return ans;
}

1 : Function Declaration

vector<int> findSmallestSetOfVertices(int n, vector<vector<int>>& edges) {

This is the function definition for `findSmallestSetOfVertices`, which takes in the number of vertices `n` and a 2D vector `edges` that represents directed edges between vertices. It returns a vector containing the smallest set of vertices that can reach all other vertices in the graph.

2 : Variable Initialization

    vector<int> ca(n, 0);

This line initializes a vector `ca` of size `n` with all values set to 0. It will be used to count the incoming edges for each vertex.

3 : Variable Initialization

    vector<int> ans;

This line initializes an empty vector `ans` to store the vertices that are part of the smallest set of vertices.

4 : Loop Iteration

    for(auto e: edges) {

This for-each loop iterates over each edge in the `edges` vector, where `e` represents each directed edge in the form of a 2-element vector (source, destination).

5 : Edge Processing

        ca[e[1]]++;

For each edge, the count of incoming edges for the destination vertex (`e[1]`) is incremented in the `ca` vector.

6 : Loop Iteration

    for(int i = 0; i< n ; i++)

This for loop iterates through all vertices from 0 to `n-1` to check which vertices have no incoming edges.

7 : Condition Check

    if(ca[i] == 0) ans.push_back(i);

If a vertex `i` has no incoming edges (i.e., `ca[i] == 0`), it is added to the `ans` vector as it is part of the smallest set of vertices.

8 : Return Statement

    return ans;

The function returns the `ans` vector, which contains the smallest set of vertices that can reach all other vertices.

Best Case: O(n + m)

Average Case: O(n + m)

Worst Case: O(n + m)

Description: The time complexity is O(n + m) where n is the number of vertices and m is the number of edges.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) for storing the incoming edges count and the result.

Leetcode 1557: Minimum Number of Vertices to Reach All Nodes

Explore →