Advertisement
Josif_tepe

Untitled

Nov 13th, 2022
817
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <stack>
  5. #include <cstring>
  6. using namespace std;
  7. int n, m;
  8. vector<int> graph[300005];
  9. int color[300005];
  10. bool visited[300005];
  11. stack<int> st;
  12. bool cycle(int node) {
  13.     color[node] = 1;
  14.     for(int i = 0; i < (int) graph[node].size(); i++) {
  15.         int neigh = graph[node][i];
  16.         if(color[neigh] == 0) {
  17.             if(cycle(neigh)) {
  18.                 return true;
  19.             }
  20.         }
  21.         else if(color[neigh] == 1) {
  22.             return true;
  23.         }
  24.     }
  25.     color[node] = 2;
  26.     return false;
  27. }
  28. void dfs(int node) {
  29.     visited[node] = true;
  30.     for(int i = 0; i < (int) graph[node].size(); i++) {
  31.         int neigh = graph[node][i];
  32.         if(!visited[neigh]) {
  33.             dfs(neigh);
  34.         }
  35.     }
  36.     st.push(node);
  37. }
  38. int main()
  39. {
  40.     cin >> n >> m;
  41.     memset(color, 0, sizeof color);
  42.     for(int i = 0; i < m; i++) {
  43.         int a, b;
  44.         cin >> a >> b;
  45.         a--; b--;
  46.         graph[a].push_back(b);
  47.     }
  48.     for(int i = 0; i < n; i++) {
  49.         if(color[i] == 0) {
  50.             if(cycle(i)) {
  51.                 cout << "IMPOSSIBLE\n";
  52.                 return 0;
  53.             }
  54.         }
  55.     }
  56.     for(int i = 0; i < n; i++) {
  57.         if(!visited[i]) {
  58.             dfs(i);
  59.         }
  60.     }
  61.     while(!st.empty()) {
  62.         cout << st.top() + 1 << " ";
  63.         st.pop();
  64.     }
  65.     return 0;
  66. }
  67.  
  68.  
  69. /*
  70.  ########
  71.  #M..A..#
  72.  #.#.M#.#
  73.  #M#..#..
  74.  #.######
  75.  
  76.  **/
  77.  
  78.  
  79.  
  80.  
  81.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement