[关闭]
@fuheimao 2015-07-26T12:13:59.000000Z 字数 803 阅读 38

Kosaraju

图论


  1. #include "iostream"
  2. #include "vector"
  3. #include "queue"
  4. #include "stack"
  5. #include "cstring"
  6. using namespace std;
  7. vector<int> Graph[1000];
  8. vector<int> OpGraph[1000];
  9. stack<int> Time;
  10. bool Visited[1000];
  11. void G_Dfs(int x){
  12. Visited[x] = true;
  13. for (std::vector<int>::iterator i = Graph[x].begin(); i != Graph[x].end(); ++i){
  14. if (!Visited[*i]){
  15. G_Dfs(*i);
  16. }
  17. }
  18. Time.push(x);
  19. }
  20. void OpG_Dfs(int x){
  21. Visited[x] = true;
  22. cout << " " << x;
  23. for (std::vector<int>::iterator i = OpGraph[x].begin(); i != OpGraph[x].end(); ++i){
  24. if (!Visited[*i]){
  25. OpG_Dfs(*i);
  26. }
  27. }
  28. }
  29. int main(int argc, char const *argv[]){
  30. int n, m;
  31. cin >> n >> m;
  32. for (int i = 0; i < m; ++i){
  33. int from, to;
  34. cin >> from >> to;
  35. Graph[from].push_back(to);
  36. OpGraph[to].push_back(from);
  37. }
  38. G_Dfs(1);
  39. memset(Visited, 0, sizeof(Visited));
  40. while (!Time.empty()){
  41. int Now = Time.top();
  42. Time.pop();
  43. if (!Visited[Now]){
  44. cout << "{";
  45. OpG_Dfs(Now);
  46. cout << " }" << endl;
  47. }
  48. }
  49. return 0;
  50. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注