拓扑排序
在无环有向图中,一条有向边s->e可以看作是一种顺序关系(s 大于 e, 或者只有当s发生后e才能发生)。假设是先后发生的约束,求得一个所有节点都发生的序列称作拓扑排序。
搜索这样一种路径我们可以从indegree为0的节点开始。
使用的数据结构
1 2
| vector<int> indegree(n) queue<int>
|
喧闹和富有
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
| class Solution { public: vector<int> loudAndRich(vector<vector<int>>& richer, vector<int>& quiet) { int n = quiet.size(); vector<vector<int>> g(n); vector<int> indegree(n,0);
vector<int> ans(n,0); for(int i = 0;i < n;++i) ans[i] = i;
for(auto& r : richer){ g[r[0]].push_back(r[1]); indegree[r[1]]++; } queue<int> q; for(int i = 0;i < n;++i){ if(!indegree[i]) q.push(i); } while(!q.empty()){ int idx = q.front();q.pop();
for(auto& to : g[idx]){ if(quiet[to] > quiet[idx]){ ans[to] = ans[idx]; quiet[to] = quiet[idx]; } indegree[to]--; if(!indegree[to]) q.push(to); } } return ans; } };
|
在提交记录中看到一个巨牛的写法: 我们是要把最小值往节点的子节点传递,假设有一条路径,开始节点是最小值,我们要把他往后传:
1
| a -> b -> c -> ... -> d -> e -> f
|
第一次扫描所有路径,由于[s,e]不一定按照顺序分布,假设我们传递到c
1
| a(min) -> b(min) -> c(min) -> ... -> d -> e ->f
|
再反过来扫描所有边,也无法传递到整个路径
构造测试用例:[[0,1],[4,5],[3,4],[1,2],[2,3],[6,7],[5,6]]
[4,0,7,3,1,5,6,2]
方法确实错了
欧拉路径
欧拉路径即从某一顶点出发,通过且通过一次所有边的一条路径。如果能够回到出发点,那么称作欧拉回路。
判断欧拉路径
对无向图:
- 如果所有的顶点度数为偶数 <=> 欧拉通路
- 如果只有两个顶点度数为奇数 <=> 欧拉路径
对于有向图:
- 如果所有顶点入度等于出度 <=> 欧拉通路
- 如果只有两个点入读与出度不等,且差为 1 和 -1 <=> 欧拉路径
找到一欧拉路径
如果存在一个欧拉路径,那么从某一点出发进行dfs,那么:
例如对下面的图:
1 2 3
| -> E -> F A -> B <-> G <-> D
|
可能先搜索到path1: ->E->F, 再搜索到path2: ->G->B->D->B
从B开始的路径就是 B + path2 + path1
如果要保证字典序,那么我们需要从字典序较小的节点进行搜索,最后再将路劲逆序,这样如果存在欧拉终点,欧拉终点是先退出的dfs,之后陆续退出的是字节序较大的点。
1 2 3
| dfs(A) -> dfs(B) -> dfs(D) -> dfs(B) -> dfs(E) -> dfs(F) -> return -> dfs(G) -> dfs(B) -> return
|
重新安排行程
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
| class Solution { public: vector<string> findItinerary(vector<vector<string>>& tickets) { sort(tickets.begin(),tickets.end()); reverse(tickets.begin(),tickets.end()); unordered_map<string,vector<string>> g; for(auto& t:tickets){ g[t[0]].push_back(t[1]); } vector<string> ans; function<void(string)> dfs = [&](string cur){ while(g[cur].size() > 0){ string next = g[cur].back(); g[cur].pop_back(); dfs(next); } ans.push_back(cur); }; dfs("JFK"); reverse(ans.begin(),ans.end()); return ans; } };
|