kananasgarli90

Condensation of the graph

Oct 26th, 2020
778
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>g[11];
  4. vector<int>gscc[11];
  5. int n, m, color[11], fin[11], id[11], t, say, u, v;
  6. set<pair<int, int> > st;
  7. //Topoloji siralama
  8. void dfs(int s){
  9.     color[s] = 1;
  10.     for(int i = 0; i < g[s].size(); i++){
  11.         int a = g[s][i];
  12.         if(color[a] == 0){
  13.             dfs(a);
  14.         }
  15.     }
  16.     fin[++t] = s;
  17. }
  18.  
  19. //SCC-DFS
  20. void dfs_scc(int s){
  21.     color[s] = 2;
  22.     id[s] = say;
  23.     for(int i = 0; i < gscc[s].size(); i++){
  24.         int a = gscc[s][i];
  25.         if(color[a] == 1){
  26.             dfs_scc(a);
  27.         }
  28.     }
  29. }
  30. int main()
  31. {
  32.     cin>>n>>m;
  33.     while(m--){
  34.         cin>>u>>v;
  35.         g[u].push_back(v);
  36.         gscc[v].push_back(u);
  37.     }
  38.  
  39.     for(int i = 1; i <= n; i++){
  40.         if(color[i] == 0){
  41.             dfs(i);
  42.         }
  43.     }
  44.  
  45.     for(int i = t; i >= 1; i--){
  46.         int a = fin[i];
  47.         if(color[a] == 1){
  48.             say++;
  49.             dfs_scc(a);
  50.         }
  51.     }
  52.     for(int i = 1; i <= n; i++){
  53.         for(int j = 0; j < g[i].size(); j++){
  54.             u = i;
  55.             v = g[i][j];
  56.             if(id[u] != id[v]){
  57.                 st.insert(make_pair(u, v));
  58.             }
  59.         }
  60.     }
  61.     cout<<st.size()<<endl;
  62. }
  63.  
RAW Paste Data