fork download
copy 
  1. from collections import defaultdict, deque
  2.  
  3. def find_order(N, M, groups, dependencies):
  4.     # Create adjacency list and count incoming edges
  5.     adj = defaultdict(list)
  6.     in_degree = [0] * N
  7.  
  8.     for a, b in dependencies:
  9.         a, b = a-1, b-1  # Convert to 0-based indexing
  10.         adj[a].append(b)
  11.         in_degree[b] += 1
  12.  
  13.     # Create priority queue (will store projects with no dependencies)
  14.     # Format: (group_id, project_id)
  15.     available = []
  16.  
  17.     # Add all projects with no dependencies initially
  18.     for i in range(N):
  19.         if in_degree[i] == 0:
  20.             available.append((groups[i], i))
  21.     available.sort()  # Sort by group_id, then project_id
  22.  
  23.     result = []
  24.  
  25.     while available:
  26.         # Take project with lowest group_id and lowest project_id
  27.         _, curr_proj = available.pop(0)
  28.         result.append(curr_proj + 1)  # Convert back to 1-based indexing
  29.  
  30.         # Process all dependencies
  31.         for next_proj in adj[curr_proj]:
  32.             in_degree[next_proj] -= 1
  33.             if in_degree[next_proj] == 0:
  34.                 available.append((groups[next_proj], next_proj))
  35.         available.sort()  # Keep the list sorted
  36.  
  37.     # Check if we used all projects
  38.     if len(result) != N:
  39.         return [-1]
  40.     return result
  41.  
  42. def main():
  43.     # Read input
  44.     N, M = map(int, input().split())
  45.     groups = list(map(int, input().split()))
  46.     dependencies = []
  47.     for _ in range(M):
  48.         a, b = map(int, input().split())
  49.         dependencies.append((a, b))
  50.  
  51.     # Find order
  52.     result = find_order(N, M, groups, dependencies)
  53.  
  54.     # Print result
  55.     if result[0] == -1:
  56.         print(-1)
  57.     else:
  58.         print(*result)
  59.  
  60. if __name__ == "__main__":
  61.     main()
Success #stdin #stdout 0.04s 9892KB
comments (?)
stdin
copy 
4 4
2 1 1 3
1 2
2 3
3 4
1 3
stdout
copy 
1 2 3 4
https://ideone.com/u78pUr
language:
Python 3 (python  3.9.5)
created:
5 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!