kosaraju算法|有向图强连通分量

简单描述kosaraju算法就两个步骤

1. 在反向图上做后根遍历，按遍历顺序把结点压栈

2. 以出栈顺序为初始节点去原图上遍历

在第二次遍历时，每次以初始节点遍历到的所有节点都和初始节点在同一个强连通分量

void dfs1(int u, const vector<vector<int>>& reverse_edges, vector<bool>& visited, stack<int>& s) {
    visited[u] = true;
    for(int v: reverse_edges[u]) {
        if(!visited[v]) {
            dfs1(v, reverse_edges, visited, s);
        }
    }
    s.push(u);
}

void dfs2(int u, const vector<vector<int>>& edges, vector<bool>& visited, int source, vector<int>& result) {
    visited[u] = true;
    result[u] = source;
    for(int v: edges[u]) {
        if(!visited[v]) {
            dfs2(v, edges, visited, source, result);
        }
    }
}

// 计算图的强联通分量
// params: edges 邻接表
// returns: 返回每个结点所在的强联通分量的代表元
//          相同代表元说明属于同一强联通分量，不同代表元说明属于不同强联通分量
//          返回的不同值的个数就是强连通分量数
vector<int> kosaraju(const vector<vector<int>>& edges) {
    int n = edges.size();
    vector<int> result(n);

    // 反向图
    vector<vector<int>> reverse_edges(n);
    for(int u=0;u<n;u++) {
        for(int v: edges[u]) {
            reverse_edges[v].push_back(u);
        }
    }

    stack<int> s;
    do {
        // 在反向图上做后根遍历，把结点压栈
        vector<bool> visited(n, false);
        for(int u=0;u<n;u++) {
            if(!visited[u]) {
                dfs1(u, reverse_edges, visited, s);
            }
        }
    } while(false);

    do {
        vector<bool> visited(n, false);
        // 这时依次按照s中弹出的结点为开始结点去遍历原图（即使用edges），就可以得到强连通分量
        while(!s.empty()) {
            int u = s.top(); s.pop();
            if(!visited[u]) {
                dfs2(u, edges, visited, u/*代表元*/, result);
            }
        }
    } while(false);
    return result;
}

有了代表元数组就可以把原图简化成一个由强连通分量构成的有向无环图，再去做进一步处理就方便了，比如拓朴排序之类的。