daily pastebin goal
3%
SHARE
TWEET

Untitled

a guest Aug 10th, 2018 56 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.  
  34. vector<pair<int, int>> edge_inside;
  35.  
  36. void set_edge_inside(int u, int v) {
  37.     edge_inside.push_back({u + 1, v + 1});
  38. }
  39.  
  40. void print_inside_edges() {
  41.     for (auto t : edge_inside) {
  42.         cout << t.first << ' ' << t.second << '\n';
  43.     }
  44. }
  45.  
  46. int init_reset_edge(int scc_num, const vector<unordered_set<int>> &ng) {
  47.     int ans = 0;
  48.     is_edge_scc.assign(scc_num, vector<int> (scc_num));
  49.     for (int i = 0; i < (int)ng.size(); i++) {
  50.         for (auto t : ng[i]) {
  51.             is_edge_scc[i][t] = 1;
  52.             ans++;
  53.         }
  54.     }
  55.     return ans;
  56. }
  57.  
  58. void reset_edge(int u, int v, vector<unordered_set<int>> &ng) {
  59.     is_edge_scc.at(u).at(v) = 0;
  60.     ng[u].erase(v);
  61. }
  62.  
  63. void set_edge(int u, int v, vector<unordered_set<int>> &ng) {
  64.     is_edge_scc.at(u).at(v) = 1;
  65.     ng[u].insert(v);
  66. }
  67.  
  68. void print_outside_edges() {
  69.     vector<int> pr(n);
  70.     for (int i = 0; i < n; i++) {
  71.         pr[colors[i]] = i;
  72.     }
  73.     for (int i = 0; i < (int)is_edge_scc.size(); i++) {
  74.         for (int j = 0; j < (int)is_edge_scc.size(); j++) {
  75.             if (is_edge_scc[i][j]) {
  76.                 auto f = pr[i];
  77.                 auto s = pr[j];
  78.                 cout << f + 1 << ' ' << s + 1 << '\n';
  79.             }
  80.         }
  81.     }
  82. }
  83.  
  84. void dfs_connected(int cur, vector<int> &used, const vector<unordered_set<int>> &ng) {
  85.     used[cur] = 1;
  86.     for (auto t : ng[cur]) {
  87.         if (!used[t]) {
  88.             dfs_connected(t, used, ng);
  89.         }
  90.     }
  91. }
  92.  
  93. bool is_connected(int u, int v, const vector<unordered_set<int>> &ng) {
  94.     int cu = colors[u];
  95.     int cv = colors[v];
  96.     vector<int> used(ng.size());
  97.     dfs_connected(cu, used, ng);
  98.     return used[cv];
  99. }
  100.  
  101. void dfs_scc_1(int cur) {
  102.     used[cur] = 1;
  103.     for (auto t : g[cur]) {
  104.         if (!used[t]) {
  105.             dfs_scc_1(t);
  106.         }
  107.     }
  108.     ord.push_back(cur);
  109. }
  110.  
  111. void dfs_scc_2(int cur, int clr, vector<int> &seen) {
  112.     used[cur] = 1;
  113.     colors[cur] = clr;
  114.     sz[clr]++;
  115.     seen.push_back(cur);
  116.     for (auto t : inv[cur]) {
  117.         if (!used[t]) {
  118.             dfs_scc_2(t, clr, seen);
  119.         }
  120.     }
  121. }
  122.  
  123. int ans_inside = 0;
  124.  
  125. vector<unordered_set<int>> scc() {
  126.     used.assign(n, 0);
  127.     for (int i = 0; i < n; i++) {
  128.         if (!used[i]) {
  129.             dfs_scc_1(i);
  130.         }
  131.     }
  132.     colors.resize(n);
  133.     used.assign(n, 0);
  134.     reverse(ord.begin(), ord.end());
  135.     int cnt = 0;
  136.     vector<int> seen;
  137.     for (auto t : ord) {
  138.         if (!used[t]) {
  139.             seen.clear();
  140.             sz.push_back(0);
  141.             dfs_scc_2(t, cnt, seen);
  142.             cnt++;
  143.             if (sz.back() != 1) {
  144.                 for (int i = 0; i < (int)seen.size(); i++) {
  145.                     set_edge_inside(seen[i], seen[(i + 1) % seen.size()]);
  146.                     ans_inside++;
  147.                 }
  148.             }
  149.         }
  150.     }
  151.     vector<unordered_set<int>> ans(cnt);
  152.     for (int i = 0; i < n; i++) {
  153.         for (auto t : g[i]) {
  154.             if (colors[i] != colors[t]) {
  155.                 ans[colors[i]].insert(colors[t]);
  156.             }
  157.         }
  158.     }
  159.     return ans;
  160. }
  161.  
  162. int solve() {
  163.     //get_cyclic_scc
  164.     vector<unordered_set<int>> ng;
  165.     ng = scc();
  166.    
  167.     int ans_outside = init_reset_edge((int)ng.size(), ng);
  168.     for (int i = 0; i < n; i++) {
  169.         for (auto t : g[i]) {
  170.             if (colors[i] != colors[t]) {
  171.                 reset_edge(colors[i], colors[t], ng);
  172.                 ans_outside--;
  173.                 auto tmp = is_connected(i, t, ng);
  174.                 if (!tmp) {
  175.                     set_edge(colors[i], colors[t], ng);
  176.                     ans_outside++;
  177.                 }
  178.             }
  179.         }
  180.     }
  181.     return ans_outside + ans_inside;
  182. }
  183.  
  184. signed main() {
  185.     ios_base::sync_with_stdio(false);
  186.     cin.tie(0);
  187.    
  188.     #ifdef LOCAL
  189.     assert(freopen("input.txt", "r", stdin));
  190.     assert(freopen("output.txt", "w", stdout));
  191.     #endif
  192.    
  193.     int m;
  194.     cin >> n >> m;
  195.     g.resize(n);
  196.     inv.resize(n);
  197.     for (int i = 0; i < m; i++) {
  198.         int u, v;
  199.         cin >> u >> v;
  200.         u--;
  201.         v--;
  202.         g[u].push_back(v);
  203.         inv[v].push_back(u);
  204.     }
  205.    
  206.     cout << solve() << endl;
  207.     print_outside_edges();
  208. //    cout << '\n';
  209.     print_inside_edges();
  210. }
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