首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
您现在的位置: 程式碼之家 >> 編程語言 >  >> C語言 >> C++ >> 關於C++

POJ 1270 Following Orders:拓撲排序全排列枚舉(DFS 回溯)

     編輯:關於C++

問題描述

給定變量集合(如 {a,b,c,d})和若干約束 x。輸出滿足所有約束的變量全排列,字典序順序。

建模:有向無環圖 (DAG) 拓撲排序

變量為節點,約束 x 為有向邊 x→y。求所有拓撲序列。

DFS 回溯枚舉所有拓撲序


int n; vector G[26]; int indeg[26];
bool used[26]; char order[26]; int idx;

void dfs() {
    if (idx == n) { print(order); return; }
    for (int i=0; i

關鍵點

  • 變量可能不連續(如 {a,c,f}),需映射到 0..n-1。
  • 按字典序遍歷候選節點,保證輸出有序。
  • 入度數組回溯時恢復。
  • 檢測環:若某步無入度為 0 的未用節點,說明有環(題目保證無環)。

複雜度

最壞 O(n!),但 n ≤ 20 且約束通常較多,實際搜索樹很小。POJ 1270 數據極弱,DFS 直接過。

  1. 上一篇文章:
  2. 下一篇文章:
Copyright © 程式碼之家 All Rights Reserved