Advertisement
Guest User

Untitled

a guest
May 24th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.75 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <list>
  4. using namespace std;
  5.  
  6. class Graph {
  7. public:
  8. Graph(int V): vert(V) {}~Graph() {}
  9. void addEdge(int u, int v) { adj[u].push_back(v); }
  10. const list<int> & edges(int u) const { return adj[u]; }
  11. bool cycle(vector < int > & path) const{// a(v) < a(u) < t(u) < t(v) // u->v
  12. dfs(p,A,T);
  13. for(int w:A){
  14. for(int k:A){
  15. if (A[k]<A[w]<T[w]<T[k]){
  16. for(int l:p){
  17. if(p[l]==w)
  18. }
  19. return true;
  20. }
  21. }
  22.  
  23. }
  24. }
  25.  
  26. private:
  27. vector<list<int>> adj;
  28. int vert;
  29. enum state {UNVISITED, SEEN, VISITED};
  30. vector<int> p,A,T;
  31. void dfs_help(int u, int & time,vector < int > & p,
  32. vector < int > & A, vector < int > & T,
  33. vector < state > & status) {
  34. status[u] = SEEN;
  35. A[u] = ++time;
  36. for (int v: edges(u))
  37. if (status[v] == UNVISITED) {
  38. p[v] = u;
  39. dfs_help(v, time, p, A, T, status);
  40. }
  41. status[u] = VISITED;
  42. T[u] = ++time;
  43. }
  44.  
  45. void dfs(vector < int > & p,
  46. vector < int > & A, vector < int > & T) {
  47. int N = vert;
  48. vector < state > status(N);
  49. for (int u = 0; u < N; ++u) {
  50. p[u] = -1;
  51. status[u] = UNVISITED;
  52. }
  53. int time = 0;
  54. for (int u = 0; u < N; ++u)
  55. if (status[u] == UNVISITED)
  56. dfs_help(u, time, p, A, T, status);
  57. }
  58.  
  59. };
  60.  
  61. int main() {
  62. int V, E;
  63. cin >> V >> E;
  64. Graph g(V);
  65. for (int i = 0; i < E; ++i) {
  66. int u, v;
  67. cin >> u >> v;
  68. g.addEdge(u, v);
  69. }
  70. vector < int > path;
  71. bool c = g.cycle(path);
  72. if (c) {
  73. cout << "CYCLE:";
  74. for (int i = 0; i < path.size(); ++i)
  75. cout << path[i] << (i == path.size() - 1 ? "\n" : "");
  76. } else {
  77. cout << "NO CYCLE" << endl;
  78. }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement