leetcode 周賽155 | 項目管理之拓撲排序演算法
- 2019 年 10 月 6 日
- 筆記
今天看了下leetcode周賽的題目，沒怎麼做，第四題是一道Hard題目，看了下題意感覺要用拓撲排序，但是這道題除了依賴關係，還有一個分組的變數，導致這道題處理起來會複雜些，可能需要2次拓撲排序或者1次複雜的拓撲排序。
下午看了下排名第一的題解，果然是2次拓撲排序，程式碼比較精簡，值得學習一下。
來看下本次比賽這道題的通過次數
，這次是真的很低。
來看題：
5200. 項目管理 顯示英文描述
公司共有 n 個項目和 m 個小組，每個項目要不沒有歸屬，要不就由其中的一個小組負責。
我們用 group[i] 代表第 i 個項目所屬的小組，如果這個項目目前無人接手，那麼 group[i] 就等於 -1。（項目和小組都是從零開始編號的）
請你幫忙按要求安排這些項目的進度，並返回排序後的項目列表：
同一小組的項目，排序後在列表中彼此相鄰。 項目之間存在一定的依賴關係，我們用一個列表 beforeItems 來表示，其中 beforeItems[i] 表示在進行第 i 個項目前（位於第 i 個項目左側）應該完成的所有項目。 結果要求：
如果存在多個解決方案，只需要返回其中任意一個即可。
如果沒有合適的解決方案，就請返回一個 空列表。
示例 1：
輸入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] 輸出：[6,3,4,1,5,2,0,7]
示例 2：
輸入：n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] 輸出：[] 解釋：與示例 1 大致相同，但是在排序後的列表中，4 必須放在 6 的前面。
大概思路：
1、首先對於所有的項目，將他們之間的依賴關係連成邊，然後進行拓撲排序，解決掉同一個組內元素先後的問題。
2、排序後，進行分組，按組的依賴關係連成邊，然後進行拓撲排序，解決掉多個組的先後問題。
3、這時候可以將排序後的組合併起來，返回即可。
源程式碼：
const int MAXN = 30010; vector<int> v[MAXN]; int deg[MAXN]; void clear(int n) { for (int i = 0; i < n; ++i) { v[i].clear(); deg[i] = 0; } } void addedge(int x, int y) { v[x].push_back(y); deg[y] ++; } int head, tail, Q[MAXN]; bool topsort(int n) { head = 1; tail = 0; for (int i = 0; i < n; ++i) if (!deg[i]) { Q[++tail] = i; } while (head <= tail) { int x = Q[head++]; for (auto y : v[x]) if (!--deg[y]) Q[++tail] = y; } return tail == n; } class Solution { public: vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) { clear(n); for (int i = 0; i < n; ++i) { for (auto x : beforeItems[i]) { //元素間的依賴關係 addedge(x, i); } } //top排序進行分組 if (!topsort(n)) return {}; int tmp_m = m; for (int i = 0; i < n; ++i) { if (group[i] == -1) { group[i] = m++; } } vector<vector<int>> v(m); for (int i = 1; i <= n; ++i) v[group[Q[i]]].push_back(Q[i]); clear(m); for (int i = 0; i < n; ++i) { for (auto x : beforeItems[i]) { if (group[x] == group[i]) continue; //組之間的依賴關係 addedge(group[x], group[i]); } } //對組進行top排序 if (!topsort(m)) return {}; vector<int> ret; //分組輸出 for (int i = 1; i <= m; ++i) { for (auto x : v[Q[i]]) ret.push_back(x); } return ret; } }; 再來回顧一下拓撲排序：
一個簡單的問題
有n個任務，用1-n進行表示，任務可能存在依賴關係，(u,v)表示v需要依賴任務u，輸出完成所有任務的序列。
拓撲排序
拓撲排序就是解決這種存在先後關係的問題的演算法。在上面的問題中，可以把每個任務看成圖上的一個節點，對於(u, v)表示 u→v。
比如有3個任務，表示為1，2，3，任務依賴關係為(2,3) (3,1) 那麼就有如下圖所示：
任務序列也就是2，3，1。對於有些圖，序列可能是多個。
在圖論中，由一個有向無環圖DAG的頂點組成的序列，當且僅當滿足下列條件時，稱為該圖的一個拓撲排序
1 每個頂點出現且只出現一次； 2 若A在序列中排在B的前面，則在圖中不存在從B到A的路徑。
卡恩演算法
卡恩於1962年提出的演算法。簡單來說就是，假設L是存放結果的列表，先找到那些入度為零的節點，把這些節點放到L中，因為這些節點沒有任何的父節點。然後把與這些節點相連的邊從圖中去掉，再尋找圖中的入度為零的節點。對於新找到的這些入度為零的節點來說，他們的父節點已經都在L中了，所以也可以放入L。重複上述操作，直到找不到入度為零的節點。如果此時L中的元素個數和節點總數相同，說明排序完成；如果L中的元素個數和節點總數不同，說明原圖中存在環，無法進行拓撲排序。
偽程式碼
bool toposort() { q = new queue(); for (i = 0; i < n; i++) if (in_deg[i] == 0) q.push(i); ans = new vector(); while (!q.empty()) { u = q.pop(); ans.push_back(u); for each edge(u, v) { if (--in_deg[v] == 0) q.push(v); } } if (ans.size() == n) { for (i = 0; i < n; i++) std::cout << ans[i] << std::endl; return true; } else { return false; } } 簡單的理解，遍歷每個節點N，從N開始進行DFS搜索，如果能夠完成搜索，則說明存在拓撲排序。如下程式碼。
// dfs 版本 bool dfs(int u) { c[u] = -1; for (int v = 0; v <= n; v++) if (G[u][v]) { if (c[v] < 0) return false; else if (!c[v]) dfs(v); } c[u] = 1; topo.push_back(u); return true; } bool toposort() { topo.clear(); memset(c, 0, sizeof(c)); for (int u = 0; u <= n; u++) if (!c[u]) if (!dfs(u)) return false; reverse(topo.begin(), topo.end()); return true; }