kananasgarli90

Condensation of the graph

Sep 23rd, 2020
480
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int>v[10001], vscc[10001];
  4. set<pair<int, int>>st;
  5. int n, m, used[10001], a, b, say, color=1;
  6. int f[10001], t;
  7. void dfs(int s){
  8.     used[s] = color;
  9.     for(int i = 0; i < v[s].size(); i++){
  10.         int node = v[s][i];
  11.         if(used[node] == 0){
  12.             dfs(node);
  13.         }
  14.     }
  15.     f[++t] = s;
  16. }
  17.  
  18. void scc_dfs(int s){
  19.     used[s] = color;
  20.     for(int i = 0; i < vscc[s].size(); i++){
  21.         int node = vscc[s][i];
  22.         if(used[node] == 1){
  23.             scc_dfs(node);
  24.         }
  25.     }
  26. }
  27. int main()
  28. {
  29.     cin>>n>>m;
  30.     while(m--){
  31.         cin>>a>>b;
  32.         v[a].push_back(b);
  33.         vscc[b].push_back(a);
  34.     }
  35.     for(int i = 1; i <= n; i++){
  36.         if(used[i] == 0){
  37.             dfs(i);
  38.         }
  39.     }
  40.     for(int i = t; i >= 1; i--){
  41.         if(used[f[i]] == 1){
  42.             color++;
  43.             scc_dfs(f[i]);
  44.             say++;
  45.         }
  46.     }
  47.     for(int i = 1; i <= n; i++){
  48.         for(int j = 0; j < v[i].size(); j++){
  49.             int node1 = i;
  50.             int node2 = v[i][j];
  51.             if(used[node1] != used[node2]){
  52.                 st.insert(make_pair(used[node1], used[node2]));
  53.             }
  54.         }
  55.     }
  56.     cout<<st.size()<<endl;
  57. }
RAW Paste Data