Advertisement
Josif_tepe

Untitled

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