现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
链接：https://leetcode.cn/problems/course-schedule-ii/description/
class Solution {public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int> res;queue<int> q;vector<multiset<int>> edges(numCourses);map<int, int> rec;for (auto& it: prerequisites) {edges[it[1]].insert(it[0]);rec[it[0]]++;}for (int i = 0; i < numCourses; ++i) {if (rec.find(i) == rec.end()) {q.push(i);}}while (!q.empty()) {int tmp = q.front();q.pop();res.push_back(tmp);for (auto& n: edges[tmp]) {rec[n]--;if (rec[n] == 0) {q.push(n);}}}if (res.size() == numCourses)return res;else return vector<int>();}};
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。
请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。
树的 高度 是指根节点和叶子节点之间最长向下路径上边的数量。
链接：https://leetcode.cn/problems/minimum-height-trees/description/
越靠近里面的节点越有可能是最小高度树的顶点。因此，不断把原来的图给剪掉一圈叶子节点，形成一个缩小的新的图。最后找到的就是两边同时向中间靠近的节点，那么这个中间节点就相当于把整个距离二分了，就是到两边距离最小的点。
class Solution {public:vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {vector<int> res;if (n == 1) {return {0};}vector<int> degree(n);vector<vector<int>> graph(n, vector<int>());for (auto& e: edges) {degree[e[0]]++;degree[e[1]]++;graph[e[0]].push_back(e[1]);graph[e[1]].push_back(e[0]);}queue<int> q;for (int i = 0; i < n; ++i) {if (degree[i] == 1) q.push(i);}while (!q.empty()) {res.clear();int len = q.size();for (int i = 0; i < len; ++i) {int tmp = q.front();q.pop();res.push_back(tmp);vector<int> neighbours = graph[tmp];for (auto& neighbour: neighbours) {degree[neighbour]--;if (degree[neighbour] == 1) {q.push(neighbour);}}}}return res;}};
给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。
链接：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/description/
将矩阵看成一个有向图，计算每个单元格对应的出度，即有多少条边从该单元格出发。从所有出度为 0 的单元格开始搜索。
class Solution {public:vector<vector<int>> dir = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};int longestIncreasingPath(vector<vector<int>>& matrix) {if (matrix.size() == 0 || matrix[0].size() == 0) {return 0;}int m = matrix.size();int n = matrix[0].size();vector<vector<int>> outdegrees(m, vector<int>(n));for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {for (int k = 0; k < 4; ++k) {int newX = i + dir[k][0];int newY = j + dir[k][1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] > matrix[i][j]) {outdegrees[i][j]++;}}}}queue<pair<int, int>> q;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (outdegrees[i][j] == 0) {q.emplace(i, j);}}}int ans = 0;while (!q.empty()) {++ans;int len = q.size();for (int i = 0; i < len; ++i) {int x, y;tie(x, y) = q.front();q.pop();for (int k = 0; k < 4; ++k) {int newX = x + dir[k][0];int newY = y + dir[k][1];if (newX >= 0 && newX < m && newY >= 0 && newY < n && matrix[newX][newY] < matrix[x][y]) {outdegrees[newX][newY]--;if (outdegrees[newX][newY] == 0) {q.emplace(newX, newY);}}}}}return ans;}};
