Salvens

E

Aug 1st, 2023 (edited)
841
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.95 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <iomanip>
  4. #include <vector>
  5. #include <array>
  6. #include <set>
  7. #include <map>
  8.  
  9. using namespace std;
  10.  
  11. #define int long long
  12.  
  13. //const long long INF = 1e18 + 7;
  14. const int MAXN = 1e5 + 100;
  15. //const int N = 1e5 + 10;
  16. //const int MOD = 1e9 + 7;
  17.  
  18. int dp[MAXN][2];
  19. vector<vector<int>> g;
  20. map<pair<int, int>, pair<int, int>> edges;
  21. map<pair<int, int>, int> pos;
  22.  
  23. void dfs(int v, int p) {
  24.     dp[v][0] = dp[v][1] = 0;
  25.     for (auto to: g[v]) {
  26.         if (to == p) continue;
  27.         dfs(to, v);
  28.         dp[v][0] = max(max(dp[v][0], dp[to][0]), dp[to][1]);
  29.         dp[v][1] = max(dp[v][1], dp[to][0]);
  30.     }
  31.     ++dp[v][1];
  32. }
  33.  
  34. vector<pair<int, pair<int, int>>> ans;
  35.  
  36. void get_ans(int v, int p = -1) {
  37.     for (auto to: g[v]) {
  38.         if (to == p) continue;
  39.         if (dp[to][1] > dp[to][0]) {
  40.             int x = min(v + 1, to + 1), y = max(v + 1, to + 1);
  41.             int x1 = edges[make_pair(x, y)].first, y1 = edges[make_pair(x, y)].second;
  42.             ans.emplace_back(make_pair(pos[make_pair(x1, y1)], make_pair(x1, y1)));
  43.         }
  44.         get_ans(to, v);
  45.     }
  46. }
  47.  
  48. bool comp(const pair<int, pair<int, int>>& lhs, const pair<int, pair<int, int>>& rhs) {
  49.     return lhs.first < rhs.first;
  50. }
  51.  
  52. signed main() {
  53.     ios_base::sync_with_stdio(false);
  54.     cin.tie(nullptr);
  55.     cout.tie(nullptr);
  56.     int n, m;
  57.     cin >> n >> m;
  58.     g.resize(n);
  59.     for (int i = 0; i < m; ++i) {
  60.         int u, v;
  61.         cin >> u >> v;
  62.         pair<int, int> tmp = make_pair(min(u, v), max(u, v));
  63.         edges[tmp] = make_pair(u, v);
  64.         pos[tmp] = i;
  65.         --u, --v;
  66.         g[u].emplace_back(v);
  67.         g[v].emplace_back(u);
  68.     }
  69.  
  70.     dfs(0, -1);
  71.  
  72.     ans.reserve(m);
  73.     get_ans(0);
  74.     cout << ans.size() << '\n';
  75.     sort(ans.begin(), ans.end(), comp);
  76.     for (int i = 0; i < (int)ans.size(); ++i) {
  77.         cout << ans[i].second.first << ' ' << ans[i].second.second << '\n';
  78.     }
  79. }
Advertisement
Add Comment
Please, Sign In to add comment