fork download
copy 
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <bits/stdc++.h>	
  3. using namespace std;
  4. typedef long long ll;
  5. typedef long double ld;
  6. typedef vector<int> vi;
  7. typedef vector<ll> vl;
  8. typedef pair<int, int>pi;
  9. typedef pair<ll, ll>pl;
  10. typedef vector<pi>vpi;
  11. typedef vector<pl>vpl;
  12. typedef vector<vi> vvi;
  13. typedef vector<vl> vvl;
  14. typedef vector<string> vs;
  15. typedef vector<bool> vb;
  16. const long double PI = acos(-1);
  17. const ll oo = 1e18 + 7;
  18. const int MOD = 1e9 + 7;
  19. const int N = 2e5 + 7;
  20. #define all(v) (v).begin(),(v).end()
  21. #define rall(v) (v).rbegin(),(v).rend()
  22. #define read(v) for (auto& it : v) scanf("%d", &it);
  23. #define readl(v) for (auto& it : v) scanf("%lld", &it);
  24. #define print(v) for (auto it : v) printf("%d ", it); puts("");
  25. #define printl(v) for (auto it : v) printf("%lld ", it); puts("");
  26. int n,m,p[N],sz[N],cnt=n,mx=1;
  27. int find(int u){
  28.     if(u==p[u])
  29.     return u;
  30.     return p[u]=find(p[u]);
  31. }
  32. void unite(int u,int v){
  33.     u=find(u),v=find(v);
  34.     if(u==v)
  35.     return;
  36.     p[v]=u;
  37.     sz[u]+=sz[v];
  38.     cnt--;
  39.     mx=max(mx,sz[u]);
  40. }
  41. void solve() {
  42.     scanf("%d %d",&n,&m);
  43.     cnt=n;
  44.     for(int i=0;i<=n;i++)
  45.     p[i]=i,sz[i]=1;
  46.     for(int i=0;i<m;i++){
  47.         int u,v;
  48.         scanf("%d %d",&u,&v);
  49.         unite(u,v);
  50.         printf("%d %d\n",cnt,mx);
  51.     }
  52.  
  53. }
  54. int t = 1;
  55. int main() {
  56. 	//scanf("%d", &t);
  57. 	while (t--) solve();
  58. }
Success #stdin #stdout 0s 5256KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/JqmaPc
language:
C++14 (gcc 8.3)
created:
1 day 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!