fork download
copy 
  1. /*
  2. 	Author: Ritik Patel
  3. */
  4.  
  5.  
  6. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& STL DEBUGGER &&&&&&&&&&&&&&&&&&&&&&&&&&&
  7.  
  8. // #define _GLIBCXX_DEBUG       // Iterator safety; out-of-bounds access for Containers, etc.
  9. // #pragma GCC optimize "trapv" // abort() on (signed) integer overflow.
  10.  
  11. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& LIBRARIES &&&&&&&&&&&&&&&&&&&&&&&&&&&
  12.  
  13. #include <bits/stdc++.h>
  14. using namespace std;
  15.  
  16. /*#include <ext/pb_ds/assoc_container.hpp> // Common file
  17. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  18. template<typename T, typename V = __gnu_pbds::null_type>
  19. using ordered_set = __gnu_pbds::tree<T, V, less<T>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>; 
  20. */
  21. //find_by_order()->returns an iterator to the k-th largest element(0-based indexing)
  22. //order_of_key()->Number of items that are strictly smaller than our item
  23.  
  24. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEFINES &&&&&&&&&&&&&&&&&&&&&&&&&&&
  25.  
  26. #define int long long int
  27. // #define ll long long int
  28. #define all(i) i.begin(), i.end()
  29. #define sz(a) (int)a.size()
  30.  
  31. // #define ld long double
  32. // const ld PI  = 3.141592;
  33. const int dx4[4] = {0, 1, 0, -1};
  34. const int dy4[4] = {-1, 0, 1, 0};
  35. const int dx8[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  36. const int dy8[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  37.  
  38. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& DEBUG &&&&&&&&&&&&&&&&&&&&&&&&&&&
  39.  
  40. #define XOX
  41. vector<string> vec_splitter(string s) {
  42.     for(char& c: s) c = c == ','?  ' ': c;
  43.     stringstream ss; ss << s;
  44.     vector<string> res;
  45.     for(string z; ss >> z; res.push_back(z));
  46.     return res;
  47. }
  48.  
  49. void debug_out(vector<string> __attribute__ ((unused)) args, __attribute__ ((unused)) int idx) { cerr << endl; }
  50. template <typename Head, typename... Tail>
  51. void debug_out(vector<string> args, int idx, Head H, Tail... T) {
  52.     if(idx > 0) cerr << ", ";
  53.     stringstream ss; ss << H;
  54.     cerr << args[idx] << " = " << ss.str();
  55.     debug_out(args, idx + 1, T...);
  56. }
  57.  
  58. #ifdef XOX
  59. #define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __VA_ARGS__)
  60. #else
  61. #define debug(...) 42
  62. #endif
  63.  
  64.  
  65. //&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& CODE &&&&&&&&&&&&&&&&&&&&&&&&&&&
  66.  
  67. const int MAXN = 1e5 + 5;
  68. const int MAXM = 1e5 + 5;
  69.  
  70. int N, M, timer, compid;
  71.  
  72. vector<pair<int, int>> g[MAXN];
  73. bool used[MAXN], isBridge[MAXM];
  74. int comp[MAXN], tin[MAXN], minAncestor[MAXN];
  75.  
  76. vector<int> tree[MAXN]; // Store 2-edge-connected component tree.(Bridge tree).
  77.  
  78. void dfs(int v, int p) {
  79.     tin[v] = minAncestor[v] = ++timer;
  80.     used[v] = 1;
  81.     for(auto &e: g[v]) {
  82.         int to, id;
  83.         tie(to, id) = e;
  84.         if(to == p) continue;
  85.         if(used[to]) {
  86.             minAncestor[v] = min(minAncestor[v], tin[to]);
  87.         } else {
  88.             dfs(to, v);
  89.             minAncestor[v] = min(minAncestor[v], minAncestor[to]);
  90.             if(minAncestor[to] > tin[v]) {
  91.                 isBridge[id] = true;
  92.             }
  93.         }
  94.     }
  95. }
  96.  
  97. void dfs1(int v, int p) {
  98.     used[v] = 1;
  99.     comp[v] = compid;
  100.     for(auto &e: g[v]) {
  101.         int to, id;
  102.         tie(to, id) = e;
  103.  
  104.         if(isBridge[id]) { // avoid traversing from this edge. so we get full component.
  105.             continue;
  106.         }
  107.         if(used[to]) {
  108.             continue;
  109.         }
  110.         dfs1(to, v);
  111.     }
  112. }
  113.  
  114. vector<pair<int, int>> edges;
  115.  
  116. void addEdge(int from, int to, int id) {
  117.     g[from].push_back({to, id});
  118.     g[to].push_back({from, id});
  119.     edges[id] = {from, to};
  120. }
  121.  
  122. void initB() {
  123.  
  124.     for(int i = 0; i <= compid; ++i)
  125.         tree[i].clear();
  126.     for(int i = 1; i <= N; ++i)
  127.         used[i] = false;
  128.     for(int i = 1; i <= M; ++i)
  129.         isBridge[i] = false;
  130.  
  131.     timer = 0;
  132.     compid = 0;
  133. }
  134.  
  135. void bridge_tree() {
  136.  
  137.     initB();
  138.  
  139.     dfs(1, -1); //Assuming graph is connected.
  140.  
  141.     for(int i = 1; i <= N; ++i)
  142.         used[i] = 0;
  143.  
  144.     for(int i = 1; i <= N; ++i) {
  145.         if(!used[i]) {
  146.             dfs1(i, -1);
  147.             ++compid;
  148.         }
  149.     }
  150.  
  151.     for(int i = 1; i <= M; ++i) {
  152.         if(isBridge[i]) {
  153.             int u, v;
  154.             tie(u, v) = edges[i];
  155.             // connect two componets using edge.
  156.             tree[comp[u]].push_back(comp[v]);
  157.             tree[comp[v]].push_back(comp[u]);
  158.         }
  159.     }
  160. }
  161.  
  162. void init() {
  163.     edges.clear(); edges.resize(M + 1);
  164.     for(int i = 1; i <= N; ++i)
  165.         g[i].clear();
  166. }
  167.  
  168. int farthest = -1, farthlvl = -1;
  169. int totalEdges = 0;
  170.  
  171. void dfs2(int v, int p, int lvl = 0) {
  172.     int child = 1;
  173.     for(auto &to: tree[v]) {
  174.         if(to == p) continue;
  175.         ++totalEdges;
  176.         ++child; dfs2(to, v, lvl + 1);
  177.     }
  178.     // If leaf node.
  179.     if(child == 1 and lvl > farthlvl)
  180.         farthest = v, farthlvl = lvl;
  181. }
  182.  
  183. int diameter = 0;
  184.  
  185. void dfs3(int v, int p, int lvl = 0) {
  186.     diameter = max(diameter, lvl);
  187.     for(auto &to: tree[v]) {
  188.         if(to == p) continue;
  189.         dfs3(to, v, lvl + 1);
  190.     }
  191. }
  192.  
  193. void solve() {
  194.     cin >> N >> M;
  195.  
  196.     init();
  197.  
  198.     for(int i = 1; i <= M; ++i) {
  199.         int u, v;
  200.         cin >> u >> v; addEdge(u, v, i);
  201.     }
  202.  
  203.  
  204.     bridge_tree();
  205.  
  206.     farthest = -1, farthlvl = -1;
  207.     totalEdges = 0, diameter = 0;
  208.     // Find diameter.
  209.     dfs2(0, -1);
  210.  
  211.     dfs3(farthest, -1);
  212.  
  213.     cout << totalEdges - diameter << '\n';
  214.  
  215.  
  216. }
  217.  
  218.  
  219.  
  220.  
  221. int32_t main(){
  222.     // freopen("input.txt","r",stdin);
  223.     // freopen("output.txt","w",stdout); 
  224.     ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
  225.     int T = 1; 
  226.     cin >> T;
  227.     for(int i = 1; i <= T; ++i){
  228.         // cout << "Case #" << i << ": ";
  229.         solve();
  230.     }
  231.     return 0;
  232. }
  233.  
  234. /*
  235. Sample inp
  236. */
Success #stdin #stdout 0s 8372KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/ONCpXb
language:
C++14 (gcc 8.3)
created:
4 years 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!