daily pastebin goal
57%
SHARE
TWEET

Untitled

a guest Aug 10th, 2018 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <ctime>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <map>
  6. #include <algorithm>
  7. #include <string>
  8. #include <cmath>
  9. #include <set>
  10. #include <unordered_set>
  11. #include <unordered_map>
  12. #include <stack>
  13. #include <cassert>
  14. #include <queue>
  15. #include <deque>
  16. #include <climits>
  17. #include <cstring>
  18. #include <random>
  19. #include <bitset>
  20.  
  21. using namespace std;
  22.  
  23. int n;
  24. vector<int> used;
  25. vector<int> ord;
  26. vector<int> colors;
  27. vector<vector<int>> g;
  28. vector<vector<int>> inv;
  29.  
  30. vector<int> sz;
  31. vector<vector<int>> is_edge_scc;
  32.  
  33. void init_reset_edge(int scc_num, const vector<unordered_set<int>> &ng) {
  34.     is_edge_scc.assign(scc_num, vector<int> (scc_num));
  35.     for (int i = 0; i < (int)ng.size(); i++) {
  36.         for (auto t : ng[i]) {
  37.             is_edge_scc[i][t] = 1;
  38.         }
  39.     }
  40. }
  41.  
  42. void reset_edge(int u, int v, vector<unordered_set<int>> &ng) {
  43.     is_edge_scc.at(u).at(v) = 0;
  44.     ng[u].erase(v);
  45. }
  46.  
  47. void set_edge(int u, int v, vector<unordered_set<int>> &ng) {
  48.     is_edge_scc.at(u).at(v) = 1;
  49.     ng[u].insert(v);
  50. }
  51.  
  52. void print_edges() {
  53.     for (int i = 0; i < (int)is_edge_scc.size(); i++) {
  54.         for (int j = 0; j < (int)is_edge_scc.size(); j++) {
  55.             if (is_edge_scc[i][j]) {
  56.                 cout << i + 1 << ' ' << j + 1 << '\n';
  57.             }
  58.         }
  59.     }
  60. }
  61.  
  62. void dfs_connected(int cur, vector<int> &used, const vector<unordered_set<int>> &ng) {
  63.     used[cur] = 1;
  64.     for (auto t : ng[cur]) {
  65.         if (!used[t]) {
  66.             dfs_connected(t, used, ng);
  67.         }
  68.     }
  69. }
  70.  
  71. bool is_connected(int u, int v, const vector<unordered_set<int>> &ng) {
  72.     int cu = colors[u];
  73.     int cv = colors[v];
  74.     vector<int> used(ng.size());
  75.     dfs_connected(cu, used, ng);
  76.     return used[cv];
  77. }
  78.  
  79. void dfs_scc_1(int cur) {
  80.     used[cur] = 1;
  81.     for (auto t : g[cur]) {
  82.         if (!used[t]) {
  83.             dfs_scc_1(t);
  84.         }
  85.     }
  86.     ord.push_back(cur);
  87. }
  88.  
  89. void dfs_scc_2(int cur, int clr) {
  90.     used[cur] = 1;
  91.     colors[cur] = clr;
  92.     sz[clr]++;
  93.     for (auto t : inv[cur]) {
  94.         if (!used[t]) {
  95.             dfs_scc_2(t, clr);
  96.         }
  97.     }
  98. }
  99.  
  100. vector<unordered_set<int>> scc() {
  101.     used.assign(n, 0);
  102.     for (int i = 0; i < n; i++) {
  103.         if (!used[i]) {
  104.             dfs_scc_1(i);
  105.         }
  106.     }
  107.     colors.resize(n);
  108.     used.assign(n, 0);
  109.     reverse(ord.begin(), ord.end());
  110.     int cnt = 0;
  111.     for (auto t : ord) {
  112.         if (!used[t]) {
  113.             sz.push_back(0);
  114.             dfs_scc_2(t, cnt);
  115.             cnt++;
  116.         }
  117.     }
  118.     vector<unordered_set<int>> ans(cnt);
  119.     for (int i = 0; i < n; i++) {
  120.         for (auto t : g[i]) {
  121.             if (colors[i] != colors[t]) {
  122.                 ans[i].insert(t);
  123.             }
  124.         }
  125.     }
  126.     return ans;
  127. }
  128.  
  129. int solve() {
  130.     //get_cyclic_scc
  131.     vector<unordered_set<int>> ng;
  132.     ng = scc();
  133.     init_reset_edge((int)ng.size(), ng);
  134.     int ans_inside = 0;
  135.     for (int i = 0; i < n; i++) {
  136.         for (auto t : g[i]) {
  137.             reset_edge(i, t, ng);
  138.             auto tmp = is_connected(i, t, ng);
  139.             if (!tmp) {
  140.                 set_edge(i, t, ng);
  141.                 ans_inside++;
  142.             }
  143.         }
  144.     }
  145.     return ans_inside;
  146. }
  147.  
  148. signed main() {
  149.     ios_base::sync_with_stdio(false);
  150.     cin.tie(0);
  151.    
  152.     #ifdef LOCAL
  153.     assert(freopen("input.txt", "r", stdin));
  154.     assert(freopen("output.txt", "w", stdout));
  155.     #endif
  156.    
  157.     int m;
  158.     cin >> n >> m;
  159.     g.resize(n);
  160.     inv.resize(n);
  161.     for (int i = 0; i < m; i++) {
  162.         int u, v;
  163.         cin >> u >> v;
  164.         u--;
  165.         v--;
  166.         g[u].push_back(v);
  167.         inv[v].push_back(u);
  168.     }
  169.    
  170.     cout << solve() << endl;
  171.     print_edges();
  172. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top