fork download
copy 
  1. #include<unordered_map>
  2. #include<unordered_set>
  3. #include<functional>
  4. #include<algorithm>
  5. #include<iostream>
  6. #include<hash_map>
  7. #include<iterator>
  8. #include<iomanip>
  9. #include<numeric>
  10. #include<cstring>
  11. #include<vector>
  12. #include<bitset>
  13. #include<string>
  14. #include<deque>
  15. #include<stack>
  16. #include<queue>
  17. #include<array>
  18. #include<cmath>
  19. #include<list>
  20. #include<map>
  21. #include<set>
  22.  
  23. #include <ext/pb_ds/assoc_container.hpp>
  24. #include <ext/pb_ds/tree_policy.hpp>
  25.  
  26. using namespace __gnu_pbds;
  27. using namespace std;
  28.  
  29. typedef long long ll;
  30. typedef unsigned long long ull;
  31. typedef double db;
  32. typedef long double ldb;
  33.  
  34. #define ordered_set tree<ll, null_type,less_equal<ll>, \
  35. rb_tree_tag,tree_order_statistics_node_update>
  36. #define pii pair<int,int>
  37. #define pll pair<ll,ll>
  38. #define inf INT32_MAX
  39. #define linf INT64_MAX
  40. #define pf push_front
  41. #define pb push_back
  42. #define ppb pop_back
  43. #define ppf pop_front
  44. #define ff first
  45. #define ss second
  46. /*ACPC 2021 ISA-*/
  47. ll fastPow(ll n,ll k/*,ll m*/){
  48.     if(k==0)return 1;
  49.  
  50.     ll res=fastPow(n,k/2/*,m*/)/*%m*/;
  51.  
  52.     res=(res*res)/*%m*/;
  53.  
  54.     if(k&1)res=(res*n)/*%m*/;
  55.  
  56.     return res/*%m*/;
  57. }
  58. ll fastPow(ll n,ll k,ll m){
  59.     if(k==0)return 1;
  60.  
  61.     ll res=fastPow(n,k/2,m)%m;
  62.  
  63.     res=(res*res)%m;
  64.  
  65.     if(k&1)res=(res*n)%m;
  66.  
  67.     return res%m;
  68. }
  69. ll calcMod(ll a,ll m){
  70.     return (a%m+m)%m;
  71. }
  72. ll Ceil(ll n,ll m){
  73.     return (n+m-1)/m;
  74. }
  75. const ll mod=1e9+7;
  76. vector<int>prt;
  77. int Find(int k){
  78.     if(prt[k]<0)return k;
  79.     return prt[k]=Find(prt[k]);
  80. }
  81. bool Union(int u,int v){
  82.     int pU=Find(u),pV=Find(v);
  83.     if(pU==pV)return 0;
  84.  
  85.     if(prt[pU]>prt[pV])swap(pU,pV);
  86.     prt[pU]+=prt[pV],prt[pV]=pU;
  87.     return 1;
  88. }
  89. bool solve(){
  90.     int n,m;
  91.     cin>>n>>m;
  92.  
  93.     prt.resize(n+1,-1);
  94.  
  95.     vector<pii>edges;
  96.  
  97.     int x=0;
  98.     for(int i=0;i<m;++i){
  99.         int u,v;
  100.         cin>>u>>v;
  101.  
  102.         if(Union(u,v)==0){
  103.             x++;
  104.         }
  105.         else{
  106.             edges.pb({u,v});
  107.         }
  108.  
  109.         for(int j=1;j<=n;++j)prt[j]=-1;
  110.  
  111.         for(const auto &[a,b]:edges){
  112.             Union(a,b);
  113.         }
  114.  
  115.         for(int k=0;k<x;++k){
  116.             set<pii>st;
  117.             for(int j=1;j<=n;++j){
  118.                 if(prt[j]<0){
  119.                     st.insert({prt[j],j});
  120.                 }
  121.             }
  122.  
  123.             auto it1=st.begin();
  124.             st.erase(st.begin());
  125.             auto it2=st.begin();
  126.  
  127.             Union(it1->ss,it2->ss);
  128.         }
  129.  
  130.         int mx=0;
  131.         for(int j=1;j<=n;++j){
  132.             if(prt[j]<0){
  133.                 mx=max(mx,abs(prt[j])-1);
  134.             }
  135.         }
  136.         cout<<mx<<"\n";
  137.     }
  138.     return 1;
  139. }
  140. int main(){
  141.     /*freopen("input.txt","r",stdin);
  142.     freopen("output.txt","w",stdout);*/
  143.  
  144.     //ios_base::sync_with_stdio(false);
  145.     //cin.tie(nullptr);
  146.  
  147.     int t=1;
  148.     //cin>>t;
  149.     while(t--){
  150.         solve();
  151.     }
  152.     return 0;
  153. }
Runtime error #stdin #stdout #stderr 0s 5520KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::length_error'
  what():  vector::_M_fill_insert
https://ideone.com/wAdd28
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!