有向图判环（leetcode207，leetcode210）

有向图判环（leetcode207，leetcode210）

有向图判环

#include <iostream>
#include <vector>
using namespace std;struct graph {int V;                    // 顶点的数量vector<vector<int>> adj;  // 邻接表数组graph(int x): V(x), adj(x) {}
};// 参数 graph 表示图，cur 表示当前顶点，vis 表示访问标记数组的引用，recStack 表示递归栈
bool dfs(graph &g, int cur, vector<bool> &vis, vector<bool> &recStack) {if (!vis[cur]) {vis[cur] = true;      // 标记当前顶点为已访问recStack[cur] = true; // 将当前顶点加入递归栈for (int nbr : g.adj[cur]) {if (!vis[nbr] && dfs(g, nbr, vis, recStack)) // 如果邻接顶点未被访问，则递归调用 dfsreturn true;else if (recStack[nbr])                      // 如果邻接顶点已经在递归栈中，则存在环return true;}}recStack[cur] = false;    // 从递归栈中移除当前顶点return false;
}bool HasCycle(graph &g) {vector<bool> vis(g.V, false);      // 初始化访问标记数组，所有顶点均未被访问vector<bool> recStack(g.V, false); // 初始化递归栈for (int cur=0; cur<g.V; cur++) {if (!vis[cur] && dfs(g, cur, vis, recStack))return true; }return false;
}int main() {int V = 4;graph g(V);g.adj[0].push_back(1);g.adj[0].push_back(2);g.adj[1].push_back(2);g.adj[2].push_back(3);// g.adj[2].push_back(0);  // 有环：0->1->2->0// g.adj[3].push_back(3);  // 有环：3->3if (HasCycle(g))cout << "有环" << endl;elsecout << "无环" << endl;return 0;
}

leetcode207

class Solution {
public:bool dfs(vector<vector<int>>& adj, int cur, vector<bool> &vis, vector<bool> &recStack) {if (!vis[cur]) {vis[cur] = true;      // 标记当前顶点为已访问recStack[cur] = true; // 将当前顶点加入递归栈for (int nbr : adj[cur])if (!vis[nbr] && dfs(adj, nbr, vis, recStack)) // 如果邻接节点未访问且有环，返回 truereturn true;else if (recStack[nbr])                        // 如果邻接顶点已经在递归栈中，则存在环return true;}recStack[cur] = false;    // 从递归栈中移除当前顶点return false;             // 没有检测到环}bool canFinish(int V, vector<vector<int>>& prerequisites) {vector<vector<int>> adj(V);      // 构建图的邻接表表示for (const auto& pre : prerequisites)adj[pre[1]].push_back(pre[0]);vector<bool> vis(V, false);      // 初始化访问标记数组，所有顶点均未被访问vector<bool> recStack(V, false); // 初始化递归栈for (int cur=0; cur <V; cur++)if (!vis[cur] && dfs(adj, cur, vis, recStack))return false; return true;}
};

leetcode210

class Solution {
public:bool dfs(vector<vector<int>>& adj, int cur, vector<bool>& vis, vector<bool>& recStack, stack<int>& topOrder) {if (!vis[cur]) {vis[cur] = true;          // 标记为已访问recStack[cur] = true;     // 标记为在递归栈中for (int nbr : adj[cur])  // 遍历当前节点的邻接节点if (!vis[nbr] && dfs(adj, nbr, vis, recStack, topOrder))return true;      // 如果邻接节点未访问且有环，返回 trueelse if (recStack[nbr])return true;      // 如果邻接节点在递归栈中，说明有环}recStack[cur] = false; // 从递归栈中移除当前节点topOrder.push(cur);    // 将当前节点加入拓扑排序栈return false;          // 没有发现环}vector<int> findOrder(int V, vector<vector<int>>& prerequisites) {vector<vector<int>> adj(V);for (const auto& pre : prerequisites)  // 构建图的邻接表表示adj[pre[1]].push_back(pre[0]); vector<bool> vis(V, false);            // 初始化访问标记数组，所有顶点均未被访问vector<bool> recStack(V, false);       // 初始化递归栈stack<int> topOrder;                   // 用于存储拓扑排序结果for (int cur = 0; cur < V; cur++)if (!vis[cur] && dfs(adj, cur, vis, recStack, topOrder))return {};                     // 如果发现环，返回空数组vector<int> result;while (!topOrder.empty()) {            // 将栈中的元素弹出，得到拓扑排序result.push_back(topOrder.top());topOrder.pop();}return result;}
};