有向图判环（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)) // 如果邻接顶点未被访问，则递归调用 dfs
                return 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->3

    if (HasCycle(g))
        cout << "有环" << endl;
    else
        cout << "无环" << 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)) // 如果邻接节点未访问且有环，返回 true
                    return 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;      // 如果邻接节点未访问且有环，返回 true
                else 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;
    }
};