图论

拓扑排序

在无环有向图中,一条有向边s->e可以看作是一种顺序关系(s 大于 e, 或者只有当s发生后e才能发生)。假设是先后发生的约束,求得一个所有节点都发生的序列称作拓扑排序。
搜索这样一种路径我们可以从indegree为0的节点开始。
使用的数据结构

1
2
vector<int> indegree(n)
queue<int> //储存入度为0的节点

喧闹和富有

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]){
// node idx is quiter than to
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;
}
};