6 拓朴排序问题

现在让我们来考虑另一个可以使用 DFS 来解决的经典范例：拓朴排序问题。想像有 N 件工作要完成，但是这些工作会有一定程度的相依性：我们可以用有向边 (i → j) 来表示依赖关系——进行工作 j 之前必须要先完成工作 i 。有没有办法快速找出一个完成工作顺序呢？任何一个满足答案的顺序我们称之为拓朴排序 (Topologocal Sort)。

考虑以下这张相依关系的图：

我们可以随意地从某个点开始进行 "反向" DFS：当我们决定要做这些工作的时候，先看看有哪些工作是得做但是还没完成的（这对应着沿着箭头的反方向、尚未探索过的点），直接递回呼叫查看他们。显然在察看完毕以後，就可以安心完成手上的工作了。

原来拓朴排序在 Leetcode 上面居然有这麽多题目... https://leetcode.com/tag/topological-sort/
那我们随意挑几题来写吧！

6.1 Leetcode 329. Longest Increasing Path in a Matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

题目叙述：要找出一个 m*n 矩阵当中最长的一条递增路线。只能沿着相邻的四个方向行走，不能踏出矩阵外。

解法：我们可以定义工作 A[i][j] 为「从 (i, j) 这格出发，能走出的最长路线长度」。要完成这个计算，就必须尝试沿着四个方向走到底能走多远，也就是说，这个 A[i][j] 的计算工作仰赖於计算其周围数值比较大的格子。换句话说，如果我们事先找出一个拓朴排序，就可以依照这个排序计算 A[i][j] 的正确数值。

想说还是放点参考程序码(C++)好了：

class Solution {
 public:
  int longestIncreasingPath(vector<vector<int>>& matrix) {
    int m = matrix.size();
    int n = matrix[0].size();
    vector<vector<int>> maxlen(m, vector<int>(n, 0));
    std::function<void(int, int)> dfs = [&](int x, int y) {
      maxlen[x][y] = 1;
      const int dx[4] = {-1, 0, 1, 0};
      const int dy[4] = {0, 1, 0, -1};
      for (int f = 0; f < 4; f++) {
        if (x + dx[f] >= 0 && x + dx[f] < m && y + dy[f] >= 0 &&
            y + dy[f] < n) {
          if (matrix[x + dx[f]][y + dy[f]] > matrix[x][y]) {
            if (maxlen[x + dx[f]][y + dy[f]] == 0) {
              dfs(x + dx[f], y + dy[f]);
            }
            maxlen[x][y] = max(maxlen[x][y], maxlen[x + dx[f]][y + dy[f]] + 1);
          }
        }
      }
    };
    int answer = 0;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++) {
        if (maxlen[i][j] == 0) dfs(i, j);
        answer = max(answer, maxlen[i][j]);
      }
    return answer;
  }
};

6.2 Leetcode 1591. Strange Printer II

https://leetcode.com/problems/strange-printer-ii/

题目叙述：有一台奇怪的印表机，每一次可以印一个新的颜色矩形，新的矩形印制时，如果那些位置原先就有矩形了，那部分就会被覆盖过去。现在给你印完的结果，请问这个结果是否真的是从这台奇怪印表机印出来的。

这题乍看之下跟图论没什麽关系，但有趣的事情是我们可以把印制矩形的相依性列出来，跑一个拓朴排序。最後再模拟一次绘制过程，检查看看是否与输入相符就可以啦！

class Solution {
 public:
  bool isPrintable(vector<vector<int>>& targetGrid) {
    // 首先找出每个矩形边界
    int m = targetGrid.size();
    int n = targetGrid[0].size();
    map<int, vector<int>> colorsBoundary;
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        if (colorsBoundary.find(targetGrid[i][j]) == colorsBoundary.end()) {
          colorsBoundary[targetGrid[i][j]] = {i, i, j, j};
        } else {
          vector<int>& bounds = colorsBoundary[targetGrid[i][j]];
          bounds[0] = min(bounds[0], i);
          bounds[1] = max(bounds[1], i);
          bounds[2] = min(bounds[2], j);
          bounds[3] = max(bounds[3], j);
        }
    // 接下来找出相依关系
    map<int, set<int>> dependencyGraph;
    for (auto it : colorsBoundary) {
      int color = it.first;
      vector<int> bounds = it.second;
      for (int i = bounds[0]; i <= bounds[1]; i++)
        for (int j = bounds[2]; j <= bounds[3]; j++)
          if (targetGrid[i][j] != color)
            dependencyGraph[targetGrid[i][j]].insert(color);
    }
    // 然後跑一次拓朴排序(或是发现图上有环，失败)
    map<int, int> visited;
    vector<int> toposort;
    bool has_cycle = false;
    std::function<void(int)> dfs = [&](int x) {
      visited[x] = 1;
      for (int y : dependencyGraph[x]) {
        if (visited.find(y) != visited.end()) {
          if (visited[y] == 1) has_cycle = true;
        } else {
          dfs(y);
        }
      }
      visited[x] = 2;
      toposort.push_back(x);
    };
    for (auto it : colorsBoundary) {
      int color = it.first;
      if (visited.find(color) == visited.end()) dfs(color);
    }
    if (has_cycle) return false;
    // 最後模拟一次画矩形的顺序
    vector<vector<int>> grid(m, vector<int>(n, 0));
    for (int color : toposort) {
      vector<int> bounds = colorsBoundary[color];
      for (int i = bounds[0]; i <= bounds[1]; i++)
        for (int j = bounds[2]; j <= bounds[3]; j++) grid[i][j] = color;
    }
    for (int i = 0; i < m; i++)
      for (int j = 0; j < n; j++)
        if (grid[i][j] != targetGrid[i][j]) return false;
    return true;
  }
};

6.X 冷笑话

如果下了绘制一张图的指令却没有画出任何东西的时候，就会感到叹息，因为生零图叹...