SHARE
TWEET

Untitled

lalalalalalalaalalla Sep 15th, 2019 86 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //
  2. //  main.cpp
  3. //  testprogram
  4. //
  5. //  Created by Yan Olerinskiy on 05/09/2019.
  6. //  Copyright © 2019 Yan Olerinskiy. All rights reserved.
  7. //
  8.  
  9. #include <iostream>
  10. #include <vector>
  11. #include <string>
  12. #include <iomanip>
  13. #include <queue>
  14. #include <cmath>
  15. #include <algorithm>
  16. #include <tuple>
  17. #include <iomanip>
  18. #include <stdio.h>
  19. #include <numeric>
  20. #include <map>
  21. #include <bitset>
  22. #include <set>
  23. #include <stack>
  24. #include <queue>
  25.  
  26. //#pragma GCC optimize("Ofast,no-stack-protector")
  27. //#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
  28. //#pragma GCC optimize("unroll-loops")
  29. //#pragma GCC optimize("fast-math")
  30. //#pragma GCC optimize("section-anchors")
  31. //#pragma GCC optimize("profile-values,profile-reorder-functions,tracer")
  32. //#pragma GCC optimize("vpt")
  33. //#pragma GCC optimize("rename-registers")
  34. //#pragma GCC optimize("move-loop-invariants")
  35. //#pragma GCC optimize("unswitch-loops")
  36. //#pragma GCC optimize("function-sections")
  37. //#pragma GCC optimize("data-sections")
  38. //#pragma GCC optimize("branch-target-load-optimize")
  39. //#pragma GCC optimize("branch-target-load-optimize2")
  40. //#pragma GCC optimize("btr-bb-exclusive")
  41.  
  42. #define int long long
  43. #define ll long long
  44. #define ull unsigned long long
  45. #define all(a) a.begin(), a.end()
  46. #define pii pair<int, int>
  47. #define pb push_back
  48. #define ld long double
  49.  
  50. using namespace std;
  51.  
  52. const int INF = 1e13;
  53. //const int mod = 2600000069;
  54. //const int p = 179;
  55.  
  56. int n, m;
  57. vector<vector<int>> g;
  58. vector<int> dp, tin, num;
  59. vector<bool> used, used1;
  60. int timer = 0, cnt = 0;
  61. map<pii, int> ww;
  62.  
  63. int dfs(int v, int p) {
  64.     used[v] = 1;
  65.     tin[v] = dp[v] = timer++;
  66.     int r = 0;
  67.     for (auto u: g[v]) {
  68.         if (u == p) continue;
  69.         if (used[u]) {
  70.             dp[v] = min(dp[v], dp[u]);
  71.         } else {
  72.             r += dfs(u, v);
  73.             if (dp[u] > tin[v]) {
  74.                 if (ww[{min(u, v), max(u, v)}] > 1) continue;
  75.                 r++;
  76.                 cnt++;
  77.             }
  78.         }
  79.     }
  80.     return r;
  81. }
  82.  
  83. signed main() {
  84.     ios_base::sync_with_stdio(0);
  85.     cin.tie(0);
  86.     cout.tie(0);
  87. //    freopen("points.in", "r", stdin);
  88. //    freopen("points.out", "w", stdout);
  89.     cin >> n >> m;
  90.     dp.resize(n);
  91.     g.resize(n);
  92.     tin.resize(n);
  93.     num.assign(n, 0);
  94.     used.assign(n, 0);
  95.     used1.assign(n, 0);
  96.     int x, y;
  97.     for (int i = 0; i < m; i++) {
  98.         cin >> x >> y;
  99.         x--;y--;
  100.         g[x].pb(y);
  101.         g[y].pb(x);
  102.         ww[{min(x, y), max(x, y)}]++;
  103.     }
  104.     int mm = 0;
  105.     for (int i = 0; i < n; i++) {
  106.         if (!used[i]) {
  107.             int q = dfs(i, -1);
  108.             mm = max(q, mm);
  109.         }
  110.     }
  111.     int m = 0;
  112.     for (int i = 0; i < n; i++) m = max(m, num[i]);
  113.     cout << cnt - mm;
  114. //    cout << cnt << " " << mm;
  115. }
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