Kosaraju

图论

#include "iostream"
#include "vector"
#include "queue"
#include "stack"
#include "cstring"
using namespace std;
vector<int> Graph[1000];
vector<int> OpGraph[1000];
stack<int> Time;
bool Visited[1000];
void G_Dfs(int x){
    Visited[x] = true;
    for (std::vector<int>::iterator i = Graph[x].begin(); i != Graph[x].end(); ++i){
        if (!Visited[*i]){
            G_Dfs(*i);
        }
    }
    Time.push(x);
}
void OpG_Dfs(int x){
    Visited[x] = true;
    cout << " " << x;
    for (std::vector<int>::iterator i = OpGraph[x].begin(); i != OpGraph[x].end(); ++i){
        if (!Visited[*i]){
            OpG_Dfs(*i);
        }
    }
}
int main(int argc, char const *argv[]){
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; ++i){
        int from, to;
        cin >> from >> to;
        Graph[from].push_back(to);
        OpGraph[to].push_back(from);
    }
    G_Dfs(1);
    memset(Visited, 0, sizeof(Visited));
    while (!Time.empty()){
        int Now  = Time.top();
        Time.pop();
        if (!Visited[Now]){
            cout << "{";
            OpG_Dfs(Now);
            cout << " }" << endl;
        }
    }
    return 0;
}