ค้นหาการเรียงลำดับงานจากการพึ่งพาที่กำหนดใน C++

สมมติว่าเรามีงานที่แตกต่างกัน งานเหล่านี้มีป้ายกำกับตั้งแต่ 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() ซึ่งจะใช้กราฟ การเริ่มต้น onpath อาร์เรย์ที่เข้าชม อาร์เรย์ toposort

• ถ้าไปที่[start] จะถูกทำเครื่องหมาย −

  • คืนค่าเท็จ

• onpath[start] :=true, visit[start] :=true

• สำหรับเพื่อนบ้านแต่ละคนในกราฟ[เริ่ม] ทำ

  • ถ้า onpath[neighbor] เป็นจริงหรือ dfs(graph, neighbour, onpath, visit, toposort) เป็นจริง −

    • คืนความจริง

  • แทรกเริ่มต้นที่ส่วนท้ายของ toposort

• กลับ onpath[start] :=false

• จากวิธีหลัก ให้ทำดังนี้ −

• graph =สร้างกราฟที่มี n จุดยอดและขอบที่จัดเก็บไว้ในอาร์เรย์ล่วงหน้า

• กำหนดลำดับชั้นของอาร์เรย์

• กำหนดอาร์เรย์ออนพาธขนาด n และเติมเท็จ

• กำหนดอาร์เรย์ที่เข้าชมขนาด n และเติมเท็จ

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า visit[i] เป็นเท็จ และ dfs(graph, i, onpath, visit, toposort) เป็นจริง −

    • คืนค่าอาร์เรย์ว่าง

• ย้อนกลับ 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