Advertisement
Guest User

Untitled

a guest
Feb 21st, 2019
86
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.43 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <stdlib.h>
  4. #include <stdio.h>
  5. #include <vector>
  6. #include <queue>
  7. using namespace std;
  8.  
  9. vector< vector<int> > G;
  10. vector<int> used;
  11. vector<int> answ;
  12. int flag = 0;
  13. int start;
  14.  
  15. void DFS (int v) {
  16.   printf("v = %d\n", v);
  17.   used[v] = 1; // 1 - gray 2 - black
  18.   for (int i = 0; i < G[v].size(); i++) {
  19.     if (flag == 1) {
  20.       answ.push_back(v + 1);
  21.       printf("continue\n");
  22.       return;
  23.     }
  24.     int to = G[v][i];
  25.     printf("to = %d \n", to);
  26.     if (used[to] == 1) {
  27.       start = to;
  28.       printf("RAISE FLAG curr %d start %d\n", v, start );
  29.       flag = 1;
  30.       break;
  31.     } else {
  32.       if (used[to] == 0) DFS (to);
  33.     }
  34.   }
  35.   used[v] = 2;
  36.   if (flag == 1) {
  37.     printf("curr %d start %d\n",v , start );
  38.     printf("PUSH\n" );
  39.     answ.push_back(v + 1);
  40.   }
  41. }
  42.  
  43. void topsort(int V) {
  44.   for (int i=0; i < V; ++i) {
  45.     if (!used[i] && !flag) {
  46.       printf("START DFS (%d)\n", i);
  47.       DFS (i);
  48.     }
  49.   }
  50. }
  51.  
  52. int main() {
  53.   ifstream fin("cycle.in");
  54.   ofstream fout("cycle.out");
  55.  
  56.   int V, E;
  57.   fin >> V >> E;
  58.  
  59.   G.resize(V);
  60.   used.resize(V, 0);
  61.  
  62.   int i, j, x, y;
  63.   for (i = 0; i < E; i++) {
  64.     fin >> x >> y;
  65.     G[x-1].push_back(y-1);
  66.   }
  67.  
  68.   topsort(V);
  69.  
  70.   if (!flag) {
  71.     fout << "NO";
  72.   } else {
  73.     fout << "YES" << endl;
  74.     for (int i = 0; i < answ.size(); i++) {
  75.       fout << answ[i] << ' ';
  76.     }
  77.   }
  78.  
  79.   return 0;
  80. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement