Advertisement
Josif_tepe

Untitled

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