fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define str string
  5. #define FOR(i,a,b) for(int i = (a) , _b = (b) ; i <= _b ; i++)
  6. #define FOD(i,a,b) for(int i = (a) , _b = (b) ; i < _b ; i++)
  7. #define REP(i,a,b) for(int i = (a) , _b = (b) ; i >= _b ; i--)
  8. #define RED(i,a,b) for(int i = (a) , _b = (b) ; i > _b ; i--)
  9. #define CL(a,x) memset(a,x,sizeof(a))
  10. #define MASK(x) (1LL << (x))
  11. #define fi first
  12. #define se second
  13. #define pii pair<int,int>
  14. #define pb push_back
  15. #define endl '\n'
  16. #define NAME
  17. using namespace std;
  18. const int N = 1e6 + 7 , MOD = 1e9 + 7;
  19. int n, m;
  20. vector<int> a[N];
  21. int timeDFS, scc_cnt;
  22. int num[N], low[N], on[N], id[N], rep[N];
  23. bool check[N];
  24. stack<int> st;
  25. vector<vector<int>> din, dout;
  26. vector<pii> res;
  27. int in[N], out[N];
  28. vector<int> dag[N];
  29.  
  30. void DFS(int u){
  31.     num[u] = low[u] = ++timeDFS;
  32.     st.push(u);
  33.     on[u] = true;
  34.     for(int v : a[u]){
  35.         if(!num[v]){
  36.             DFS(v);
  37.             low[u] = min(low[u], low[v]);
  38.         }
  39.         else if(on[v])low[u] = min(low[u], num[v]);
  40.     }
  41.     if(low[u] == num[u]){
  42.         ++scc_cnt;
  43.         rep[scc_cnt] = u;
  44.         while(true){
  45.             int v = st.top();
  46.             st.pop();
  47.             on[v] = 0;
  48.             id[v] = scc_cnt;
  49.             if(u == v) break;
  50.         }
  51.     }
  52. }
  53.  
  54. void BFS(int st){
  55.     queue<int> q;
  56.     q.push(st);
  57.     check[st] = true;
  58.     vector<int> d1, d2;
  59.     while(!q.empty()){
  60.         int u = q.front(); q.pop();
  61.         if(in[u] == 0)d1.pb(u);
  62.         if(out[u] == 0)d2.pb(u);
  63.         for(int v : dag[u])if(!check[v]){
  64.             q.push(v);
  65.             check[v] = true;
  66.         }
  67.     }
  68.     din.pb(d1);
  69.     dout.pb(d2);
  70. }
  71. void process(){
  72.     if(scc_cnt == 1)return;
  73.     vector<int> remain_in, remain_out;
  74.     int temp1 = -1, temp2 = -1;
  75.     FOD(i,0,din.size()){
  76.         int s = din[i].back();din[i].pop_back();
  77.         int t = dout[i].back();dout[i].pop_back();
  78.         if(i == 0)temp1 = s;
  79.         else res.pb({temp2, s});
  80.         temp2 = t;
  81.         for(int x : din[i])remain_in.pb(x);
  82.         for(int x : dout[i])remain_out.pb(x);
  83.     }
  84.     res.pb({temp2, temp1});
  85.     FOD(i,0,max(remain_in.size(), remain_out.size())){
  86.         int u = (i < (int)remain_out.size()) ? remain_out[i] : temp2;
  87.         int v = (i < (int)remain_in.size()) ? remain_in[i] : temp1;
  88.         res.pb({u, v});
  89.     }
  90. }
  91. void load(){
  92.     FOR(i,1,n)if(!num[i])DFS(i);
  93.     FOR(u,1,n)for(int v : a[u])if(id[u] != id[v]){
  94.         in[id[v]]++;
  95.         out[id[u]]++;
  96.         dag[id[u]].pb(id[v]);
  97.         dag[id[v]].pb(id[u]);
  98.     }
  99.  
  100.     FOR(i,1,scc_cnt){
  101.         sort(dag[i].begin(), dag[i].end());
  102.         dag[i].erase(unique(dag[i].begin(), dag[i].end()), dag[i].end());
  103.     }
  104.  
  105.     FOR(i,1,scc_cnt)if(!check[i])BFS(i);
  106. }
  107.  
  108. void debug(){
  109.     cout << "-----------------------" << endl;
  110.     FOR(i,1,n)cout << i << " : " << id[i] << endl;
  111.     cout << endl << endl;
  112.     cout << "din : ";
  113.     FOD(i,0,din.size())for(int u : din[i])cout << u << "(" << rep[u] << ")  ";
  114.     cout << endl;
  115.     cout << "dout : ";
  116.     FOD(i,0,dout.size())for(int u : dout[i])cout << u << "(" << rep[u] << ")  ";
  117.     cout << endl << endl;
  118.     cout << "-----------------------" << endl;
  119. }
  120.  
  121. int main(){
  122.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  123.     cin >> n >> m;
  124.     FOR(i,1,m){
  125.         int u, v; cin >> u >> v;
  126.         a[u].pb(v);
  127.     }
  128.     load();
  129.     //debug();
  130.     process();
  131.     cout << res.size() << endl;
  132.     for(pii x : res)cout << rep[x.fi] << " " << rep[x.se] << endl;
  133.     return 0;
  134. }
  135. /*
  136. 7 8
  137. 1 2
  138. 2 3
  139. 3 1
  140. 1 4
  141. 3 4
  142. 5 6
  143. 6 7
  144. 5 7
  145. */
  146.  
Success #stdin #stdout 0.02s 54136KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
0 0
https://ideone.com/vMNFry
language:
C++14 (gcc 8.3)
created:
5 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!