Advertisement
OIQ

task2270

OIQ
Nov 9th, 2019
160
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. struct color {
  7.     int a;
  8.     int b;
  9. };
  10.  
  11. vector <vector<int>> edges;
  12. vector <color> visited;
  13.  
  14. bool dfs(int v) {
  15.     if (visited[v].a == 1 && visited[v].b != 1) {
  16.         return true;
  17.     }
  18.  
  19.     if (visited[v].b == 1) {
  20.         return false;
  21.     }
  22.  
  23.     visited[v].a = 1;
  24.     for (int i = 0; i < edges[v].size(); i++) {
  25.         if (dfs(edges[v][i]))
  26.             return true;
  27.     }
  28.  
  29.     visited[v].b = 1;
  30.     return false;
  31. }
  32.  
  33. void dfs1(int v) {
  34.     if (visited[v].b == 1) {
  35.         return;
  36.     }
  37.     visited[v].b = 1;
  38.     cout << v << " ";
  39.  
  40.     for (int i = 0; i < edges[v].size(); i++) {
  41.         if (visited[edges[v][i]].b != 1) {
  42.             dfs1(edges[v][i]);
  43.             return;
  44.         }
  45.     }
  46.        
  47.    
  48. }
  49.  
  50. int main() {
  51.  
  52.     int n, m;
  53.  
  54.     cin >> n >> m;
  55.  
  56.     visited.resize(n + 1);
  57.     edges.resize(n + 1);
  58.     int a, b;
  59.  
  60.     for (int i = 1; i <= m; i++) {
  61.         cin >> a >> b;
  62.         edges[a].push_back(b);
  63.     }
  64.  
  65.     for (int i = 1; i <= n; i++) {
  66.         visited[i].a = 0;
  67.         visited[i].b = 0;
  68.     }
  69.  
  70.  
  71.     int ind = -1;
  72.  
  73.     for (int i = 1; i <= n; i++) {
  74.         if (dfs(i)) {
  75.             ind = i;
  76.             break;
  77.         }
  78.     }
  79.  
  80.     if (ind == -1)
  81.         cout << "NO";
  82.     else {
  83.         cout << "YES" << endl;
  84.         int check = ind;
  85.         vector<bool> flag(n + 1, false);
  86.  
  87.         while (!flag[check]) {
  88.             flag[check] = true;
  89.             cout << check << " ";
  90.  
  91.             for (int i = 0; i < edges[check].size(); i++)
  92.                 if (flag[i] == false && visited[edges[check][i]].b != 1) {
  93.                     check = edges[check][i];
  94.                     break;
  95.                 }
  96.  
  97.         }
  98.     }
  99.  
  100.    
  101.  
  102.     return 0;
  103. }
Advertisement
RAW Paste Data Copied
Advertisement