fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <stdio.h>
  3.  
  4. #define __Shibae__      signed main()
  5. #define IOS             ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  6. #define fiopen(Path)    freopen(Path".INP", "r", stdin); freopen(Path".OUT", "w", stdout);
  7. #define fipen(Path)     freopen(Path".INP", "r", stdin);
  8. #define sz(s)           (int)s.size()
  9. #define all(x)          x.begin(), x.end()
  10. #define maxHeap         priority_queue<int>
  11. #define minHeap         priority_queue<int, vector<int>, greater<int>>
  12. #define getBit(x, k)    (((x) >> (k)) & 1)
  13. #define MASK(i)         (1LL << (i))
  14. #define SQR(x)          (1LL * ((x) * (x)))
  15. #define db              double
  16. #define ld              long double
  17. #define ui              unsigned int
  18. #define ll              long long
  19. #define ii              pair<int, int>
  20. #define pli             pair<ll, int>
  21. #define pil             pair<int, ll>
  22. #define pll             pair<ll, ll>
  23. #define fi              first
  24. #define se              second
  25.  
  26. #define FOR(i, a, b)    for(int i = a, _b = b; i <= _b; i += 1)
  27. #define FOD(i, a, b)    for(int i = a, _b = b; i >= _b; i -= 1)
  28. #define REP(i, a)       for(int i = 0, _a = a; i < _a; i++)
  29. #define pb              push_back
  30. #define fau(u, a)       for(auto &u : a)
  31. #define debug           return cout << "debug", void();
  32.  
  33. using namespace std;
  34.  
  35. const ll mod = 1e9 + 7;
  36. const int INF = 1e9 + 7;
  37. const ll INFLL = (ll)2e18 + 7LL;
  38. const ld PI = acos(-1);
  39. const int MAX = 5e5+5;
  40.  
  41. const int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
  42. const int dy[] = {0, 0, 1, -1, -1, -1, 1, 1};
  43.  
  44. mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
  45.  
  46. ll Rand(ll l, ll r) 
  47. {
  48.     return uniform_int_distribution<ll>(l, r)(rd);
  49. }
  50.  
  51. template<class SHIBA, class ENGINE>
  52.     bool minimize(SHIBA &x, const ENGINE y)
  53.     {
  54.         if(x > y)
  55.         {
  56.             x = y;
  57.             return true;
  58.         } 
  59.         else return false;
  60.     }
  61. template<class SHIBA, class ENGINE>
  62.     bool maximize(SHIBA &x, const ENGINE y)
  63.     {
  64.         if(x < y)
  65.         {
  66.             x = y;
  67.             return true;
  68.         }
  69.         else return false;
  70.     }
  71.  
  72.  
  73. /* Template by: Nguyen Nhat Anh from Luong Van Chanh High School for the gifted */
  74. /* From Min Tuoi with love */
  75.         /**       TRY HARD        **/
  76.         /**          ORZ          **/
  77.  
  78. /* -----------------[ MAIN CODE ]----------------- */
  79.  
  80. int n, m;
  81. vector<ii> g[MAX];
  82. vector<int> adj[MAX];
  83. int num[MAX], low[MAX], timer;
  84. int cmp[MAX], cnt;
  85. stack<int> st;
  86. bool vis[MAX];
  87.  
  88. void input()
  89. {
  90.     cin >> n >> m;
  91.  
  92.     FOR(i, 1, m)
  93.     {
  94.         int u, v; cin >> u >> v;
  95.         g[u].pb({v, i});
  96.         g[v].pb({u, i});
  97.     }
  98. }
  99.  
  100. void dfs(int u, int pre)
  101. {
  102.     num[u] = low[u] = ++timer;
  103.     st.push(u);
  104.     for (auto [v, id] : g[u])
  105.     {
  106.         if (id == pre) continue;
  107.         if (num[v]) low[u] = min(low[u], num[v]);
  108.         else
  109.         {
  110.             dfs(v, id);
  111.             low[u] = min(low[u], low[v]);
  112.         }
  113.     }
  114.     if (num[u] == low[u])
  115.     {
  116.         ++cnt;
  117.         int v = -36;
  118.         while(v != u)
  119.         {
  120.             v = st.top();
  121.             cmp[v] = cnt;
  122.             num[v] = low[v] = n+1;
  123.             st.pop();
  124.         }
  125.     }
  126. }
  127.  
  128. ii dfss(int u, int pre)
  129. {
  130.     ii res = {0, u};
  131.     fau(v, adj[u])
  132.     {
  133.         if (v == pre) continue;
  134.         ii tmp = dfss(v, u);
  135.         tmp.fi++;
  136.         maximize(res, tmp);
  137.     }
  138.     return res;
  139. }
  140.  
  141. void mark(int u, int pre)
  142. {
  143.     vis[u] = 1;
  144.     fau(v, adj[u])
  145.     {
  146.         if (v == pre) continue;
  147.         mark(v, u);
  148.     }
  149. }
  150.  
  151. int get(int root)
  152. {
  153.     mark(root, -1);
  154.     ii tt = dfss(root, -1);
  155.  
  156.    return dfss(tt.se, -1).fi;
  157. }
  158.  
  159. void solve()
  160. {
  161.     FOR(i, 1, n) if (!num[i]) dfs(i, -1);
  162.     FOR(i, 1, n)
  163.     {
  164.         for (auto [v, id] : g[i])
  165.         {
  166.             if (cmp[i] != cmp[v])
  167.             {
  168.                 adj[cmp[i]].pb(cmp[v]);
  169.             }
  170.         }
  171.     }
  172.     FOR(i, 1, cnt) 
  173.     {
  174.         sort(all(adj[i]));
  175.         adj[i].resize(unique(all(adj[i])) - adj[i].begin());
  176.     }
  177.     int res = 0;
  178.     FOR(i, 1, cnt) if (!vis[i]) maximize(res, get(i));
  179.     cout << res;
  180. }
  181.  
  182. __Shibae__
  183. {
  184.     IOS
  185.  
  186.     const bool multitest = 0;
  187.     int tt = 1; if(multitest) cin >> tt;
  188.  
  189.     while( tt-- ){
  190.         input();
  191.         solve();
  192.         if(tt) cout << "\n";
  193.     }
  194.  
  195.     return 0;
  196. }
Success #stdin #stdout 0.01s 27232KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/tVcCT9
language:
C++ (gcc 8.3)
created:
21 hours 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!