2876. Count Visited Nodes in a Directed Graph

Description

There is a directed graph consisting of n nodes numbered from 0 to n - 1 and n directed edges.

You are given a 0-indexed array edges where edges[i] indicates that there is an edge from node i to node edges[i].

Consider the following process on the graph:

• You start from a node x and keep visiting other nodes through edges until you reach a node that you have already visited before on this same process.

Return an array answer where answer[i] is the number of different nodes that you will visit if you perform the process starting from node i.

 

Example 1:

Input: edges = [1,2,0,0]
Output: [3,3,3,4]
Explanation: We perform the process starting from each node in the following way:
- Starting from node 0, we visit the nodes 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 3.
- Starting from node 1, we visit the nodes 1 -> 2 -> 0 -> 1. The number of different nodes we visit is 3.
- Starting from node 2, we visit the nodes 2 -> 0 -> 1 -> 2. The number of different nodes we visit is 3.
- Starting from node 3, we visit the nodes 3 -> 0 -> 1 -> 2 -> 0. The number of different nodes we visit is 4.

Example 2:

Input: edges = [1,2,3,4,0]
Output: [5,5,5,5,5]
Explanation: Starting from any node we can visit every node in the graph in the process.

 

Constraints:

• n == edges.length
• 2 <= n <= 105
• 0 <= edges[i] <= n - 1
• edges[i] != i

 

Solutions

Solution: Topological Sort + Depth-First Search

• Time complexity: O(n)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} edges
 * @return {number[]}
 */
const countVisitedNodes = function (edges) {
  const n = edges.length;
  const indegrees = Array.from({ length: n }, () => 0);
  const seen = Array.from({ length: n }, () => false);
  const nonCycleNodes = [];
  const result = Array.from({ length: n }, () => 0);
  let queue = [];

  for (const node of edges) {
    indegrees[node] += 1;
  }

  for (let node = 0; node < n; node++) {
    if (!indegrees[node]) {
      queue.push(node);
    }
  }

  while (queue.length) {
    const nextQueue = [];

    for (const node of queue) {
      const neighbor = edges[node];

      indegrees[neighbor] -= 1;

      if (!indegrees[neighbor]) {
        nextQueue.push(neighbor);
      }

      nonCycleNodes.push(node);
      seen[node] = true;
    }

    queue = nextQueue;
  }

  const fillCycle = node => {
    let current = node;
    let visitedNodes = 0;

    while (!seen[current]) {
      visitedNodes += 1;
      seen[current] = true;
      current = edges[current];
    }

    result[node] = visitedNodes;
    current = edges[node];

    while (current !== node) {
      result[current] = visitedNodes;
      current = edges[current];
    }
  };

  for (let node = 0; node < n; node++) {
    if (!seen[node]) {
      fillCycle(node);
    }
  }

  for (let index = nonCycleNodes.length - 1; index >= 0; index--) {
    const node = nonCycleNodes[index];

    result[node] = result[edges[node]] + 1;
  }

  return result;
};