Advertisement
danya11334

Untitled

Feb 20th, 2025
113
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.20 KB | None | 0 0
  1. from collections import defaultdict, deque
  2. import sys
  3.  
  4. def main():
  5.     # Чтение входных данных из stdin
  6.     lines = sys.stdin.read().splitlines()
  7.  
  8.     # Создание графа зависимостей
  9.     graph = defaultdict(list)
  10.     in_degree = defaultdict(int)
  11.  
  12.     for line in lines:
  13.         if '->' in line:
  14.             # Извлечение зависимостей
  15.             parts = line.strip().split('->')
  16.             u = parts[0].strip().strip('"')
  17.             v = parts[1].split('[')[0].strip().strip('"')
  18.             graph[u].append(v)
  19.             in_degree[v] += 1
  20.             if u not in in_degree:
  21.                 in_degree[u] = 0
  22.  
  23.     # Топологическая сортировка с использованием BFS
  24.     queue = deque([node for node in in_degree if in_degree[node] == 0])
  25.     result = []
  26.  
  27.     while queue:
  28.         node = queue.popleft()
  29.         result.append(node)
  30.         for neighbor in graph[node]:
  31.             in_degree[neighbor] -= 1
  32.             if in_degree[neighbor] == 0:
  33.                 queue.append(neighbor)
  34.  
  35.     # Вывод результата
  36.     for package in result[::-1]:
  37.         print(package)
  38.  
  39.  
  40. main()
  41.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement