@fuheimao
2015-07-26T20:13:59.000000Z
字数 803
阅读 594
图论
#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;
}