本文共 8521 字，大约阅读时间需要 28 分钟。
There are a total of n courses you have to take, labeled from 0 to n-1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.
There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.
思路：
建立邻接表，对于每个入度为0的点执行DFS算法，如果执行过程中发现回边（访问某个结点时，prev值确定时，post值还未确定），或者执行结束后有课程没有访问到，说明无法上完所有课程。
(prev和post是什么？)
我们知道，有向图中对边的分类有：
树边：DFS森林的实际组成部分
前向边：DFS树中从一个顶点指向该顶点的一个非子项顶点后裔的边
回边：DFS树中从一个顶点指向其祖先的边
横跨边：从一个顶点指向一个已完全访问过的顶点的边。
我们可以通过一个变量clock来记录访问各个结点和离开各个结点的时间，
prev[v] = clock++;DFS(v);post[v] = clock++;
通过这些时间点，我们就可以确定边的种类。如果访问一个结点时，该结点已有prev值，但没有post值，说明是一条回边；如果该结点的prev值和post值都已经有了，若边的起始结点的prev值比要访问的结点的prev值小，说明是前向边，反之则是横跨边。
代码：
class Solution {private: vector result; int prev[5000] = {0}; int post[5000] = {0}; bool stop = false;public: vector findOrder(int numCourses, vector >& prerequisites) { int degree[5000] = {0}; vector > adj(numCourses); for(auto &i: prerequisites) { degree[i.first]++; adj[i.second].push_back(i.first); } int i; int flag = 0; for(i = 0; i < numCourses; i++) { if(degree[i] == 0 && stop == false) { //从所有入度为0的点开始DFS DFS(i, adj); flag = 1; } if(i == numCourses-1 && flag == 0) return {}; } if(stop) return {}; for(int j = 0; j < numCourses; j++) //存在孤立点 if(degree[j] == 0) result.push_back(j); if(result.size() != numCourses) //有课程未上完 return {}; vector v; for(auto j = result.rbegin(); j != result.rend(); j++) v.push_back(*j); return v; } void DFS(int node, vector >& adj) { for(auto& i: adj[node]) { if(stop) return; if(prev[i] == 1 && post[i] == 0) { //看是否存在回边 stop = true; return; } prev[i] = 1; DFS(i, adj); post[i] = 1; if(find(result.begin(),result.end(), i) == result.end()) //防止重复添加 result.push_back(i); } }}; Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.
Example:
Givena / b = 2.0, b / c = 3.0. queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? . return [6.0, 0.5, -1.0, 1.0, -1.0 ]. 思路：难点主要在于想到转化为图的问题。给定A / B = k， 即A到B有一条权为k的有向边，B到A有一条权为1/k的有向边。求A / C 的值即为求一条A到C的路径，路径上的权值的乘积就是答案。（在DFS时要注意回边，代码中采用的是每次访问完一条边就将边删除，所以每次查询都要用一张新的图）
代码：
class Solution {private: vector result; bool stop = true;public: vector calcEquation(vector > equations, vector & values, vector > queries) { int size = equations.size(); map > > adj; for(int i=0; i < size; i++) { adj[equations[i].first].push_back(pair (equations[i].second, values[i])); adj[equations[i].second].push_back(pair (equations[i].first, 1/values[i])); } for(auto& i:queries) { if(adj.find(i.first) == adj.end() || adj.find(i.second) == adj.end()) { result.push_back(-1.0); } else if(i.first == i.second) { result.push_back(1.0); } else { if(stop == false) result.push_back(-1.0); stop = false; map > > tmp = adj; DFS(i.first, i.second, 1.0, tmp); } } if(stop == false) result.push_back(-1.0); return result; } void DFS(string node, string& des, double count, map > >& adj) { if(stop) return; if(node == des) { stop = true; result.push_back(count); return; } for(auto i = adj[node].begin(); i != adj[node].end(); ) { auto t = *i; adj[node].erase(i); DFS(t.first, des, count*t.second, adj); } }};
In this problem, a rooted tree is a directed graph such that, there is exactly one node (the root) for which all other nodes are descendants of this node, plus every node has exactly one parent, except for the root node which has no parents.
The given input is a directed graph that started as a rooted tree with N nodes (with distinct values 1, 2, ..., N), with one additional directed edge added. The added edge has two different vertices chosen from 1 to N, and was not an edge that already existed.
The resulting graph is given as a 2D-array of edges. Each element of edges is a pair [u, v] that represents a directed edge connecting nodes u and v, where u is a parent of child v.
Return an edge that can be removed so that the resulting graph is a rooted tree of N nodes. If there are multiple answers, return the answer that occurs last in the given 2D-array.
思路：先理解题目所指的2D-arrray，实际上并不是二维矩阵那样用0,1表示连接，输入的还是往常的点对。题目要求删掉一条变后使得图成为根树。那么存在两种情况，有一个结点入度为2或者存在环。对于第一种情况，删掉其中一条边，BFS看能否遍历全部结点，如果不能就是另一条边。
class Solution {public: vector findRedundantDirectedConnection(vector >& edges) { int size = edges.size(); vector in(size); vector out(size); vector > adj(size+1); for(int i = 0; i < size; i++) { out[edges[i][0]-1]++; in[edges[i][1]-1]++; adj[edges[i][0]].push_back(edges[i][1]); } if(find(in.begin(), in.end(), 2) != in.end()) { int j; for(j = 0; j < size; j++) if(in[j] == 2) break; for(int i = size-1; i >=0; i--) { if(edges[i][1] == j+1) { in[edges[i][1]-1]--; int k; for(k = 0; k < size; k++) if(in[k] == 0) break; int num = 0; BFS(k+1, edges[i][0], edges[i][1], num, adj); if(num == size) return {edges[i][0],j+1}; else in[edges[i][1]-1]++; } } } else { for(int i = size-1; i >= 0; i--) if(in[edges[i][0]-1] == out[edges[i][0]-1] == in[edges[i][1]-1] == 1) return {edges[i][0],edges[i][1]}; } return {}; } void BFS(int node, int& from, int& to, int& count, vector >& adj) { queue q; q.push(node); while(!q.empty()) { int front = q.front(); q.pop(); count++; for(auto i:adj[front]) { if(front == from && i == to) continue; q.push(i); } } }}; There are N network nodes, labelled 1 to N.
Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.
Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.
思路：即找到图中某个点到其他所有点的路径，从中选取耗时最长的路径 。可以使用Dijkstra算法求出到所有点的dist值。
Dijkstra算法伪代码
代码：
使用vector
struct dist { int node; int length;};bool cmp(const dist a, const dist b) { return a.length 使用优先队列
priority_queue 对于pair<int,int> 会根据first进行排序，priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq 中的greater使得排序为从小到大。
class Solution {public: int networkDelayTime(vector >& times, int n, int k) { vector >> adj(n+1); for(auto&i:times) { adj[i[0]].push_back({i[1], i[2]}); } vector dist(n+1, 6000); dist[k] = 0; priority_queue , vector >, greater >> pq; pq.push(pair (0,k)); while(!pq.empty()) { pair p = pq.top(); pq.pop(); for(auto&i:adj[p.second]) { if(dist[i.first] > dist[p.second] + i.second) { dist[i.first] = dist[p.second] + i.second; pq.push(pair (dist[i.first], i.first)); } } } int max = 0; dist.erase(dist.begin()); for(auto& i:dist) max = i>max?i:max; if(max == 6000) return -1; else return max; }};