c++寻找强连通分量

在C++中，寻找有向图的强连通分量（Strongly Connected Components, SCC）通常使用Tarjan算法或Kosaraju算法。以下是使用Tarjan算法寻找强连通分量的示例代码：

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

class Graph {
    int V; // 顶点数
    vector<int> *adj; // 邻接表
    void SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]);

public:
    Graph(int V);
    void addEdge(int v, int w);
    void SCC();
};

Graph::Graph(int V) {
    this->V = V;
    adj = new vector<int>[V];
}

void Graph::addEdge(int v, int w) {
    adj[v].push_back(w);
}

void Graph::SCCUtil(int u, int disc[], int low[], stack<int> *st, bool stackMember[]) {
    static int time = 0;
    disc[u] = low[u] = ++time;
    st->push(u);
    stackMember[u] = true;

    for (auto v : adj[u]) {
        if (disc[v] == -1) {
            SCCUtil(v, disc, low, st, stackMember);
            low[u] = min(low[u], low[v]);
        } else if (stackMember[v]) {
            low[u] = min(low[u], disc[v]);
        }
    }

    int w = 0;
    if (low[u] == disc[u]) {
        while (st->top() != u) {
            w = st->top();
            cout << w << " ";
            stackMember[w] = false;
            st->pop();
        }
        w = st->top();
        cout << w << endl;
        stackMember[w] = false;
        st->pop();
    }
}

void Graph::SCC() {
    int *disc = new int[V];
    int *low = new int[V];
    bool *stackMember = new bool[V];
    stack<int> *st = new stack<int>();

    for (int i = 0; i < V; i++) {
        disc[i] = -1;
        low[i] = -1;
        stackMember[i] = false;
    }

    for (int i = 0; i < V; i++)
        if (disc[i] == -1)
            SCCUtil(i, disc, low, st, stackMember);
}

int main() {
    Graph g(5);
    g.addEdge(1, 0);
    g.addEdge(0, 2);
    g.addEdge(2, 1);
    g.addEdge(0, 3);
    g.addEdge(3, 4);

    cout << "强连通分量如下：" << endl;
    g.SCC();

    return 0;
}

这段代码定义了一个Graph类，并实现了Tarjan算法来寻找强连通分量。`SCCUtil`函数是Tarjan算法的核心实现，`SCC`函数则是对外的接口。