MinhNGUYEN2k4

Untitled

Sep 27th, 2021 (edited)
199
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.50 KB | None | 0 0
  1. //Nguyen Huu Hoang Minh
  2. #include <bits/stdc++.h>
  3. #define sz(x) int(x.size())
  4. #define all(x) x.begin(),x.end()
  5. #define reset(x) memset(x, 0,sizeof(x))
  6. #define pb push_back
  7. #define mp make_pair
  8. #define fi first
  9. #define se second
  10. #define N 50005
  11. #define remain(x) if (x > MOD) x -= MOD
  12. #define ii pair<int, int>
  13. #define iiii pair< ii , ii >
  14. #define viiii vector< iiii >
  15. #define vi vector<int>
  16. #define vii vector< ii >
  17. #define bit(x, i) (((x) >> (i)) & 1)
  18. #define Task "test"
  19. #define int long long
  20.  
  21. using namespace std;
  22.  
  23. typedef long double ld;
  24. const int inf = 1e10;
  25. const int minf = -1e10;
  26.  
  27. int n, m;
  28. vector<ii> g[N];
  29. int cau[100005];
  30. int num[N], low[N], cnt;
  31. vector<int> g2[N];
  32. vector<int> g3[N];
  33. struct edge{
  34.     int u, v;
  35. } e[100005];
  36. int root;
  37. int st[100005];
  38. int sn;
  39.  
  40. int tplt;
  41. int dai_dien[10005];
  42. int head[10005];
  43.  
  44. void dfs(int u, int pre){
  45.     num[u] = low[u] = ++cnt;
  46.     for(auto i : g[u]){
  47.         int v = i.fi;
  48.         int id = i.se;
  49.         if (v==pre) continue;
  50.         if (num[v]) low[u] = min(low[u],num[v]);
  51.         else{
  52.             dfs(v,u);
  53.             low[u] = min(low[u],low[v]);
  54.             if (low[v]>=num[v]){
  55.                 cau[id] = 1;
  56.             }
  57.         }
  58.     }
  59. }
  60.  
  61. void readfile()
  62. {
  63.     ios_base::sync_with_stdio(false);
  64.     cin.tie(0);cout.tie(0);
  65.     if (fopen(Task".inp","r"))
  66.     {
  67.         freopen(Task".inp","r",stdin);
  68.         //freopen(Task".out","w",stdout);
  69.     }
  70.     cin >> n >> m;
  71.     for(int i=1; i<=m; i++){
  72.         int u, v;
  73.         cin >> u >> v;
  74.         g[u].pb(ii(v,i));
  75.         g[v].pb(ii(u,i));
  76.         e[i] = {u,v};
  77.     }
  78. }
  79.  
  80. void DFS(int u){
  81.     dai_dien[u] = tplt;
  82.     for(auto v : g2[u]){
  83.         if (!dai_dien[v]){
  84.             DFS(v);
  85.         }
  86.     }
  87. }
  88.  
  89. vector<int> leaf;
  90.  
  91. void DFS_arrange(int u, int pre){
  92.     for(auto v : g3[u]){
  93.         if (v!=pre){
  94.             DFS_arrange(v,u);
  95.         }
  96.     }
  97.     if (g3[u].size()==1 && u!=1) leaf.pb(u);
  98. }
  99.  
  100. void proc()
  101. {
  102.     for(int i=1; i<=n; i++){
  103.         if (num[i]==0){
  104.             dfs(i,i);
  105.         }
  106.     }
  107.     for(int i=1; i<=m; i++){
  108.         if (!cau[i]){
  109.             int u = e[i].u;
  110.             int v = e[i].v;
  111.             g2[u].pb(v);
  112.             g2[v].pb(u);
  113.         }
  114.     }
  115.     for(int i=1; i<=n; i++){
  116.         if (!dai_dien[i]){
  117.             ++tplt;
  118.             head[tplt] = i;
  119.             DFS(i);
  120.         }
  121.     }
  122.     for(int i=1; i<=n; i++){
  123.         int u = dai_dien[i];
  124.         for(auto j : g[i]){
  125.             int v = j.fi;
  126.             v = dai_dien[v];
  127.             if (u!=v){
  128.                 g3[u].pb(v);
  129.                 g3[v].pb(u);
  130.             }
  131.         }
  132.     }
  133.     for(int i=1; i<=tplt; i++){
  134.         if (g3[i].size()){
  135.             sort(all(g3[i]));
  136.             g3[i].erase(unique(all(g3[i])),g3[i].end());
  137.         }
  138.     }
  139.  
  140.  
  141.     // phần này là nối nè gs :v phần trên đệ nén đồ thị
  142.     vector<ii> res;
  143.     DFS_arrange(1,1);
  144.     for(auto x : leaf){
  145.         if (sn < 3){
  146.             st[++sn] = x;
  147.         }
  148.         if (sn==3){
  149.             int u = head[st[1]];
  150.             int v = head[st[3]];
  151.             res.pb(ii(u,v));
  152.             st[1] = st[2];
  153.             sn = 1;
  154.         }
  155.     }
  156.     if (sn==2){
  157.         res.pb(ii(head[st[1]],head[st[2]]));
  158.     }
  159.     if (sn==1 || g3[1].size()==1){
  160.         res.pb(ii(head[st[1]],1));
  161.     }
  162.  
  163.     cout << res.size() << '\n';
  164.     for(auto tmp : res) cout << tmp.fi << ' ' << tmp.se << '\n';
  165. }
  166.  
  167. signed main()
  168. {
  169.     readfile();
  170.     proc();
  171.     return 0;
  172. }
  173.  
Add Comment
Please, Sign In to add comment