Skip to content

2876. Count Visited Nodes in a Directed Graph 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
 public:
  vector<int> countVisitedNodes(vector<int>& edges) {
    const int n = edges.size();
    vector<int> ans(n);
    vector<int> inDegree(n);
    vector<bool> seen(n);
    queue<int> q;
    stack<int> stack;

    for (const int v : edges)
      ++inDegree[v];

    // Topology
    for (int i = 0; i < n; ++i)
      if (inDegree[i] == 0)
        q.push(i);

    // Push non-cyclic nodes to stack.
    while (!q.empty()) {
      const int u = q.front();
      q.pop();
      if (--inDegree[edges[u]] == 0)
        q.push(edges[u]);
      stack.push(u);
      seen[u] = true;
    }

    // Fill the length of cyclic nodes.
    for (int i = 0; i < n; ++i)
      if (!seen[i])
        fillCycle(edges, i, seen, ans);

    // Fill the length of non-cyclic nodes.
    while (!stack.empty()) {
      const int u = stack.top();
      stack.pop();
      ans[u] = ans[edges[u]] + 1;
    }

    return ans;
  }

 private:
  void fillCycle(const vector<int>& edges, int start, vector<bool>& seen,
                 vector<int>& ans) {
    int cycleLength = 0;
    for (int u = start; !seen[u]; u = edges[u]) {
      ++cycleLength;
      seen[u] = true;
    }
    ans[start] = cycleLength;
    for (int u = edges[start]; u != start; u = edges[u])
      ans[u] = cycleLength;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
  public int[] countVisitedNodes(List<Integer> edges) {
    final int n = edges.size();
    int[] ans = new int[n];
    int[] inDegree = new int[n];
    boolean[] seen = new boolean[n];
    Queue<Integer> q = new ArrayDeque<>();
    Stack<Integer> stack = new Stack<>();

    for (int v : edges)
      ++inDegree[v];

    // Topology
    for (int i = 0; i < n; ++i)
      if (inDegree[i] == 0)
        q.add(i);

    // Push non-cyclic nodes to stack.
    while (!q.isEmpty()) {
      int u = q.poll();
      if (--inDegree[edges.get(u)] == 0)
        q.add(edges.get(u));
      stack.push(u);
      seen[u] = true;
    }

    // Fill the length of cyclic nodes.
    for (int i = 0; i < n; ++i)
      if (!seen[i])
        fillCycle(edges, i, seen, ans);

    // Fill the length of non-cyclic nodes.
    while (!stack.isEmpty()) {
      int u = stack.pop();
      ans[u] = ans[edges.get(u)] + 1;
    }

    return ans;
  }

  private void fillCycle(List<Integer> edges, int start, boolean[] seen, int[] ans) {
    int cycleLength = 0;
    for (int u = start; !seen[u]; u = edges.get(u)) {
      ++cycleLength;
      seen[u] = true;
    }
    ans[start] = cycleLength;
    for (int u = edges.get(start); u != start; u = edges.get(u))
      ans[u] = cycleLength;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution:
  def countVisitedNodes(self, edges: List[int]) -> List[int]:
    n = len(edges)
    ans = [0] * n
    inDegree = [0] * n
    seen = [False] * n
    stack = []

    for v in edges:
      inDegree[v] += 1

    # Topology
    q = collections.deque([i for i, d in enumerate(inDegree) if d == 0])

    # Push non-cyclic nodes to stack.
    while q:
      u = q.popleft()
      inDegree[edges[u]] -= 1
      if inDegree[edges[u]] == 0:
        q.append(edges[u])
      stack.append(u)
      seen[u] = True

    # Fill the length of cyclic nodes.
    for i in range(n):
      if not seen[i]:
        self._fillCycle(edges, i, seen, ans)

    # Fill the length of non-cyclic nodes.
    while stack:
      u = stack.pop()
      ans[u] = ans[edges[u]] + 1

    return ans

  def _fillCycle(self, edges: List[int], start: int, seen: List[bool], ans: List[int]) -> None:
    cycleLength = 0
    u = start
    while not seen[u]:
      cycleLength += 1
      seen[u] = True
      u = edges[u]
    ans[start] = cycleLength
    u = edges[start]
    while u != start:
      ans[u] = cycleLength
      u = edges[u]