Leetcode # 2876. Count Visited Nodes in a Directed Graph

2023.10.01
★★★ Hard LeetCode Topology

Problem

https://leetcode.com/contest/weekly-contest-365/problems/count-visited-nodes-in-a-directed-graph/

Testcases

#	Input	Expected
1	[7,0,7,0,5,3,3,0]	[2,3,3,3,5,4,4,2]
	[3,6,1,0,5,7,4,3]	[2,7,8,2,5,4,6,3]
	[8,17,14,8,14,12,16,11,4,14,19,6,8,8,2,10,2,1,1,18]	[5,2,2,5,3,6,4,6,4,3,5,5,5,5,2,6,3,2,3,4]
	[6,3,6,1,0,8,0,6,6]	[2,2,3,2,3,4,2,3,3]

First Solution

Time Complexity: O()
Space Complexity: O()
(The input and output generally do not count towards the space complexity.)

class Solution:
  def countVisitedNodes(self, edges: List[int]) -> List[int]:
    n = len(edges)
    result = [0] * n
    
    internals = set(edges)
    externals = set(i for i in range(n)) - internals
      
    def cal_len(node):
      nonlocal result, externals, internals
      
      passed_n, visited, curr = 0, {}, node
      while curr not in visited:
        visited[curr] = passed_n
        passed_n += 1
        curr = edges[curr]
      result[node] = passed_n
      
      cycle_start_i, cycle_start_node = visited[curr], curr
      result[cycle_start_node] = passed_n - cycle_start_i
      curr = edges[node]
      for j in range(1, passed_n):
        if curr in externals:
          externals.remove(curr)
        if curr in internals:
          internals.remove(curr)
        if curr != cycle_start_node:
          if result[curr] != 0: break
          result[curr] = result[cycle_start_node] + ((cycle_start_i - j) if j < cycle_start_i else 0)
        curr = edges[curr]
    
    while externals:
      cal_len(externals.pop())
    while internals:
      cal_len(internals.pop())
    
    return result

Last Updated on 2023/10/01 by A1go