Submission #16489054

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

struct UnionFind {
  vector<int> d;
  UnionFind(int n=0): d(n,-1) {}
  int find(int x) {
    if (d[x] < 0) return x;
    return d[x] = find(d[x]);
  }
  bool unite(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return false;
    if (d[x] > d[y]) swap(x,y);
    d[x] += d[y];
    d[y] = x;
    return true;
  }
  bool same(int x, int y) { return find(x) == find(y);}
  int size(int x) { return -d[find(x)];}
};

int main(void){
    int N, M;
    cin >> N >> M;

    UnionFind union_find = UnionFind(N);

    rep(i, M){
        int A, B;
        cin >> A >> B;
        union_find.unite(A, B);
    }

    int max_group = 0;
    rep(i, N){
        if(union_find.size(i)>max_group){
            max_group = union_find.size(i);
        }
    }

    cout << max_group << endl;


}

Submission Info

Judge Result