fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. const int N = 1e5 + 5;
  7. vector<int> G[N], g[N];
  8. int n, m;
  9. int num[N], low[N], color[N], stt = 0, scc = 0, Bridge = 0;
  10. stack<int> stk;
  11. void dfs(int u, int pre) {
  12.     num[u] = low[u] = ++stt;
  13.     stk.push(u);
  14.     for (int v: G[u]) {
  15.         if (v == pre) {
  16.             pre = 0;
  17.             continue;
  18.         }
  19.         if (!num[v]) {
  20.             dfs(v, u);
  21.             low[u] = min(low[u], low[v]);
  22.  
  23.             if (low[v] > num[u]) {
  24.                 Bridge++;
  25.                 int i;
  26.                 ++scc;
  27.                 do {
  28.                     i = stk.top(); stk.pop();
  29.                     color[i] = scc;
  30.                 } while(i != v);
  31.             }
  32.         }
  33.         else low[u] = min(low[u], num[v]);
  34.     }
  35. }
  36. void BridgeTree() {
  37.     for (int u = 1; u <= n; u++) {
  38.         for (int v: G[u]) if (color[u] != color[v]) {
  39.             g[color[u]].push_back(color[v]);
  40.         }
  41.     }
  42. }
  43.  
  44. int Node, maxLen;
  45. void dfsFurthest(int u, int pre, int len) {
  46.     num[u] = 1;
  47.     if (len > maxLen) maxLen = len, Node = u;
  48.     for (int v: g[u]) if (v != pre) dfsFurthest(v, u, len + 1);
  49. }
  50.  
  51. void solve() {
  52.     cin >> n >> m;
  53.     stk = {};
  54.     for (int i = 1; i <= n; i++) {
  55.         G[i] = g[i] = {};
  56.         num[i] = low[i] = color[i] = 0;
  57.     }
  58.     stt = scc = Bridge = 0;
  59.     for (int i = 1; i <= m; i++) {
  60.         int u, v; cin >> u >> v;
  61.         G[u].push_back(v);
  62.         G[v].push_back(u);
  63.     }
  64.     for (int i = 1; i <= n; i++) if (!num[i]) dfs(i, i);
  65.     BridgeTree();
  66.     int ans = 0;
  67.     fill(num + 1, num + n + 1, 0);
  68.     for (int u = 1; u <= n; u++) if (!num[u]) {
  69.         int A = u;
  70.         Node = A, maxLen = 0;
  71.         dfsFurthest(A, A, 0);
  72.         A = Node;
  73.         dfsFurthest(A, A, 0);
  74.         ans = max(ans, maxLen);
  75.     }
  76.     cout << Bridge - ans << "\n";
  77. }
  78.  
  79. signed main() {
  80.     cin.tie(NULL)->sync_with_stdio(false);
  81.     if(ifstream("Input.inp")) {
  82.         freopen("Input.inp", "r", stdin);
  83.         freopen("Output.out", "w", stdout);
  84.     }
  85.     int tt; cin >> tt;
  86.     while(tt--) {
  87.         solve();
  88.     }
  89.     return 0;
  90. }
Success #stdin #stdout 0.01s 8260KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/13z3Xv
language:
C++14 (gcc 8.3)
created:
8 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!