[Algorithm] Topological Sort

위상 정렬

• 조건 : DAG(directed acyclic graph)
  • 방향 O, 싸이클 X
• BFS 구현

  1. in_degree[i] : 정점 i로 들어오는 가장자리 수

  2. in_degree[i] = 0 인 정점 visit 표시 후 queue에 정점 추가

  3. !queue.empty() 순회

     dequeue()한 정점에 인접한 정점 중 방문하지 않은 정점의 in_degree 하나 감소

     in_degree 감소 후 값이 0이면 해당 정점은 q.push()후 방문 표시

• 모든 원소 방문하기 전에 queue가 빈다면 → 싸이클 존재
• 코드

  for (int i = 0; i < M; i++) {
      int K; cin >> K;
      int prev, cur;
      cin >> prev;
      for (int j = 1; j < K; j++) {
          cin >> cur;
          indegree[cur]++;
          adj[prev].push_back(cur);
          prev = cur;
      }
  }
  
  queue<int> q;
  // 들어오는 정점이 없는 노드 추가
  for (int i = 1; i <= N; i++) {
      if (indegree[i] == 0) q.push(i);
  }
  
  vector<int> ans;
  while(!q.empty()) {
      int cur = q.front();
      q.pop();
      // dequeue한 순서 = 위상 정렬 순서
      ans.push_back(cur);
  		
  		// 인접한 정점 하나씩 감소 -> 0이면 push
      for (int nxt: adj[cur]) {
          if (--indegree[nxt] == 0) q.push(nxt);
      }
  }
  
  if (ans.size() != N) {
      cout << 0 << '\n';
  } else {
      for (int i = 0; i < N; i++) {
          cout << ans[i] << '\n';
      }
  }