fork download
copy 
  1. import sys
  2. from collections import defaultdict
  3.  
  4. # First DFS to compute the finish time order
  5. def dfs_first(graph, node, visited, stack):
  6.     visited.add(node)
  7.     for neighbor in graph[node]:
  8.         if neighbor not in visited:
  9.             dfs_first(graph, neighbor, visited, stack)
  10.     stack.append(node)
  11.  
  12. # Second DFS on the transposed graph to find SCCs
  13. def dfs_second(transposed_graph, node, visited):
  14.     visited.add(node)
  15.     for neighbor in transposed_graph[node]:
  16.         if neighbor not in visited:
  17.             dfs_second(transposed_graph, neighbor, visited)
  18.  
  19. # Kosaraju's Algorithm to find SCCs
  20. def kosaraju_scc(graph, n):
  21.     # Step 1: Perform first DFS to get the finishing times
  22.     visited = set()
  23.     stack = []
  24.  
  25.     for node in range(n):
  26.         if node not in visited:
  27.             dfs_first(graph, node, visited, stack)
  28.  
  29.     # Step 2: Transpose the graph (reverse all edges)
  30.     transposed_graph = defaultdict(list)
  31.     for node in graph:
  32.         for neighbor in graph[node]:
  33.             transposed_graph[neighbor].append(node)
  34.  
  35.     # Step 3: Perform DFS on the transposed graph in order of decreasing finish times
  36.     visited.clear()  # Reset visited for the second DFS
  37.     scc_count = 0
  38.  
  39.     while stack:
  40.         node = stack.pop()
  41.         if node not in visited:
  42.             dfs_second(transposed_graph, node, visited)
  43.             scc_count += 1  # Each DFS from an unvisited node is a new SCC
  44.  
  45.     return scc_count
  46.  
  47. # Read input
  48. input_lines = sys.stdin.read().splitlines()
  49. index = 0
  50. graphs = []
  51.  
  52. # Parse input to create graphs
  53. while index < len(input_lines):
  54.     n = int(input_lines[index])  # Number of nodes
  55.     index += 1
  56.     graph = defaultdict(list)
  57.  
  58.     for i in range(n):
  59.         neighbors = list(map(int, input_lines[index].split()))
  60.         graph[i] = neighbors
  61.         index += 1
  62.  
  63.     graphs.append((graph, n))
  64.  
  65. # Process each graph to compute the number of SCCs
  66. results = []
  67. for graph, n in graphs:
  68.     scc_count = kosaraju_scc(graph, n)
  69.     results.append(scc_count)
  70.  
  71. # Output the results
  72. for result in results:
  73.     print(result)
  74.  
Success #stdin #stdout 0.03s 9916KB
comments (?)
stdin
copy 
3
1
2
0 1
5
1 3
0 2
3
0 1
2 3
8
2 3
2
0 3
2
2 3

7
6
0
stdout
copy 
1
2
5
0
https://ideone.com/GrDHgf
language:
Python 3 (python  3.9.5)
created:
81 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!