标签：ret font 拓扑 col break 课程 算法 map 比较
【207】 Course Schedule
排课问题，n门课排课，有的课程必须在另外一些课程之前上，问能不能排出来顺序。
题解：裸的拓扑排序。参考代码见算法竞赛入门指南这本书。
1 class Solution {
2 public:
3 bool dfs(const vectorint>>& g, vectorint>& c, int u) {
4 c[u] = -1;
5 for (int v = 0; v v) {
6 if (g[u][v]) {
7 if (c[v] 0) { return false; }
8 else if (!c[v] && !dfs(g, c, v)) {
9 return false;
10 }
11 }
12 }
13 c[u] = 1;
14 topo[--t] = u;
15 return true;
16 }
17 bool canFinish(int numCourses, vectorint, int>>& prerequisites) {
18 vectorint>> graph(numCourses, vectorint>(numCourses, 0));
19 n = numCourses;
20 topo.resize(n);
21 t = n;
22 for (auto ele : prerequisites) {
23 int u = ele.first, v = ele.second;
24 graph[v][u] = 1;
25 }
26 vectorint> c(n, 0);
27 for (int i = 0; i i) {
28 if (!c[i]) {
29 if (!dfs(graph, c, i)) {
30 return false;
31 }
32 }
33 }
34 /*
35 for (int i = 0; i 36 cout 37 }
38 cout 39 */
40 return true;
41 }
42 vectorint> topo;
43 int n, t;
44 };
View Code
【210】 Course Schedule II
同上一个排课问题，这次的问题是能不能给出一个可行的顺序。
题解：还是裸的拓扑排序。
1 class Solution {
2 public:
3 bool dfs(vectorint>& c, vectorint>& topo, int u) {
4 c[u] = -1;
5 for (int v = 0; v v) {
6 if (g[u][v]) {
7 if (c[v] 0) {return false;}
8 else if (!c[v] && !dfs(c, topo, v)) {return false; }
9 }
10 }
11 c[u] = 1;
12 topo[--t] = u;
13 return true;
14 }
15 vectorint> findOrder(int numCourses, vectorint, int>>& prerequisites) {
16 n = numCourses, t = n;
17 vectorint> topo(n, 0);
18 vectorint> c(n, 0);
19 vectorint>> graph(n, vectorint>(n, 0));
20 for (auto ele : prerequisites) {
21 int u = ele.first, v = ele.second;
22 graph[v][u] = 1;
23 }
24 g = graph;
25
26 for (int u = 0; u u) {
27 if (!c[u]) {
28 if (!dfs(c, topo, u)) {
29 vectorint> temp;
30 return temp;
31 }
32 }
33 }
34 return topo;
35 }
36 int n, t;
37 vectorint>> g;
38 };
View Code
【269】 Alien Dictionary
给了一门新的语言，给了一个单词字典，所有的单词按照字典序排序。要求返回现有字母的顺序，没有顺序的话，返回空数组。
题解：逐个比较两个相邻的单词，如果他们第i个位置不同，说明前一个单词的第i个字母u，要小于后一个单词的第i个字母v，然后建图，建完图直接裸的拓扑排序。
1 class Solution {
2 public:
3 bool dfs(int u) {
4 c[u] = -1;
5 for (int v = 0; v v) {
6 if (g[u][v]) {
7 if (c[v] 0) {return false;}
8 else if (!c[v] && !dfs(v)) {return false;}
9 }
10 }
11 c[u] = 1;
12 topo[--cur] = u;
13 return true;
14 }
15
16 string alienOrder(vectorstring>& words) {
17 vectorint, int>> order;
18 const int n = words.size();
19 int t = 0;
20 for (int i = 0; i i) {
21 string word = words[i];
22 for (auto ele : word) {
23 if (mpCh2Num.find(ele) == mpCh2Num.end()) {
24 mpCh2Num[ele] = t;
25 mpNum2Ch[t] = ele;
26 ++t;
27 }
28 }
29 }
30 c.resize(t), topo.resize(t);
31 tot = t; cur = t;
32
33 for (int i = 0; i 1; ++i) {
34 string word1 = words[i], word2 = words[i+1];
35 for (int idx = 0; idx idx) {
36 if (word1[idx] != word2[idx]) {
37 pairint, int> p = make_pair(mpCh2Num[word1[idx]], mpCh2Num[word2[idx]]);
38 order.push_back(p);
39 break;
40 }
41 }
42 }
43
44 vectorint>> graph(t, vectorint>(t, 0));
45 for (auto ele : order) {
46 int u = ele.first, v = ele.second;
47 graph[u][v] = 1;
48 }
49 g = graph;
50
51 for (int u = 0; u u) {
52 if (!c[u]) {
53 if (!dfs(u)) {
54 string temp;
55 return temp;
56 }
57 }
58 }
59 string ans;
60 for (auto ele : topo) {
61 ans += mpNum2Ch[ele];
62 }
63 return ans;
64 }
65 vectorint>> g;
66 vectorint> c, topo;
67 mapint, char> mpNum2Ch;
68 mapchar, int> mpCh2Num;
69 int tot;
70 int cur;
71 };
View Code
【329】 Longest Increasing Path in a Matrix
给了一个矩阵matrix， 一个点他可以朝着上下左右四个方向走，问这个矩阵能走出来的最长递增的路径的长度是多少。
题解：裸的dfs会超时，所以加上了一个记忆化数组过了。题目的解法三有拓扑排序的相关解法，下次要搞懂那个解法。
1 class Solution {
2 public:
3 void print(vectorint>>& mat) {
4 const int n = mat.size(), m = mat[0].size();
5 for (int i = 0; i i) {
6 for (int j = 0; j j) {
7 cout " ";
8 }
9 cout endl;
10 }
11 }
12 int dirx[4] = {-1, 0, 1, 0};
13 int diry[4] = {0, -1, 0, 1};
14 int dfs(const vectorint>>& mat, int x, int y, vectorint>>& vis) {
15 vis[x][y] = 1;
16 for (int i = 0; i 4; ++i) {
17 int newx = x + dirx[i], newy = y + diry[i];
18 if (newx >= 0 && newx = 0 && newy mat[x][y]) {
19 if (memo[newx][newy] != 0) {
20 memo[x][y] = max(memo[x][y], memo[newx][newy] + 1);
21 } else {
22 memo[x][y] = max(memo[x][y], dfs(mat, newx, newy, vis) + 1);
23 }
24 }
25 }
26 vis[x][y] = 0;
27 return memo[x][y];
28 }
29 int longestIncreasingPath(vectorint>>& matrix) {
30 n = matrix.size();
31 if (n == 0) { return 0; }
32 m = matrix[0].size();
33 if (m == 0) { return 0; }
34
35 int ans = 0;
36 memo = matrix;
37 for (int i = 0; i i) {
38 for (int j = 0; j j) {
39 memo[i][j] = 0;
40 }
41 }
42
43 for (int i = 0; i i) {
44 for (int j = 0; j j) {
45 vectorint>> vis(n, vectorint>(m, 0));
46 memo[i][j] = dfs(matrix, i, j, vis);
47 ans = max(ans, memo[i][j]);
48 }
49 }
50 return ans +1;
51 }
52 int n, m;
53 vectorint>> memo;
54 };
View Code
【444】 Sequence Reconstruction
【LeetCode】拓扑排序
标签：ret font 拓扑 col break 课程 算法 map 比较
原文地址：https://www.cnblogs.com/zhangwanying/p/9655103.html