C++에서 주어진 종속성에서 작업 순서 찾기

n개의 다른 작업이 있다고 가정합니다. 이러한 작업은 0에서 n-1까지 레이블이 지정됩니다. 일부 작업에는 전제 조건 작업이 있을 수 있으므로 예를 들어 작업 2를 선택하려면 먼저 작업 1을 완료해야 합니다. 이 작업은 쌍으로 표시됩니다. [2, 1] 총 작업 수와 목록이 있는 경우 전제 조건 쌍 중에서 모든 작업을 완료하려면 작업 순서를 찾아야 합니다. 올바른 주문이 두 개 이상 있는 경우 그 중 하나만 반품할 수 있습니다. 그리고 주어진 모든 작업을 완료하는 것이 불가능한 경우 빈 배열을 반환합니다.

따라서 입력이 n =4이고 A =[[1, 0], [2, 0], [3, 2], [3, 1],[4,2]]인 경우 출력은 다음과 같습니다. [0, 2, 1, 4, 3]

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• dfs() 함수를 정의하면 그래프, 시작, 경로, 방문한 배열, 배열 toposort가 필요합니다.

• 방문[시작]이 표시되면 -

  • 거짓 반환

• onpath[시작] :=참, 방문[시작] :=참

• 그래프[start]의 각 이웃에 대해 수행

  • onpath[neighbor]가 참이거나 dfs(graph, Neighbor, onpath, Visited, toposort)가 참이면 -

    • true를 반환

  • toposort의 끝에 시작 삽입

• 반환 경로[시작] :=false

• 기본 방법에서 다음을 수행하십시오 -

• graph =사전 배열에 저장된 n개의 꼭짓점과 가장자리로 그래프 생성

• 배열 토폴로지 정의

• 크기가 n인 배열 경로를 정의하고 false로 채우기

• 크기가 n인 방문 배열을 정의하고 false로 채우기

• initialize i :=0의 경우, i

  • Visited[i]가 거짓이고 dfs(graph, i, onpath, Visited, toposort)가 참이면 -

    • 빈 배열 반환

• 배열 toposort 반전

• 리턴 토포소트

예

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
vector<unordered_set<int> > create_graph(int n, vector<pair<int, int> >& pre) {
   vector<unordered_set<int> > graph(n);
   for (auto pre : pre)
      graph[pre.second].insert(pre.first);
   return graph;
}
bool dfs(vector<unordered_set<int> >& graph, int start,vector<bool>& onpath, vector<bool>& visited, vector<int>& toposort) {
   if (visited[start])
      return false;
   onpath[start] = visited[start] = true;
   for (int neigh : graph[start])
      if (onpath[neigh] || dfs(graph, neigh, onpath, visited, toposort))
         return true;
   toposort.push_back(start);
   return onpath[start] = false;
}
vector<int> get_order(int n, vector<pair<int, int> > &pre){
   vector<unordered_set<int> > graph = create_graph(n, pre);
   vector<int> toposort;
   vector<bool> onpath(n, false), visited(n, false);
   for (int i = 0; i < n; i++)
      if (!visited[i] && dfs(graph, i, onpath, visited, toposort))
         return {};
   reverse(toposort.begin(), toposort.end());
   return toposort;
}
int main() {
   int n = 4;
   vector<pair<int, int> > pre = {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}};
   vector<int> v = get_order(n, pre);
   for (int i = 0; i < v.size(); i++) {
      cout << v[i] << " ";
   }
}

입력

4, {{1, 0}, {2, 0}, {3, 2}, {3, 1},{4,0}}

출력

0 1 4 2 3