Submission #521339

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i, n) for(int (i) = 0; (i) < (int)(n); ++(i))
#define rep1(i, n) for(int (i) = 1; (i) <= (int)(n); ++(i))
#define all(a) (a).begin(),(a).end()
using namespace std;
typedef long long int lli;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<lli> vlli;
typedef vector<vector<int>> vvi;
typedef vector<vector<double>> vvd;

vi par;
vi rank_of_tree;

void init(int N){
	par.resize(N);
	rank_of_tree.resize(N);
	for (int i = 0; i < N; ++i) par[i] = i;
}

//木の根を求める
int find(int x){
	if (par[x] == x){
		return x;
	}
	else {
		return par[x] = find(par[x]); //経路圧縮
	}
}

// xとyが同じグループに属するか否か
bool same(int x, int y){
	return find(x) == find(y);
}

// xとyの属するグループを併合
void merge(int x, int y){
	int px = find(x);
	int py = find(y);
	if (px == py) return;

	if (rank_of_tree[px] < rank_of_tree[py]){
		par[px] = py;
	}
	else {
		par[py] = px;
		if (rank_of_tree[px] == rank_of_tree[py]) ++rank_of_tree[px];
	}
}

int main(){
  int N, M;
  cin >> N >> M;
  init(N);
  rep(i, M){
    int x, y;
    cin >> x >> y;
    x--; y--;
    merge(x, y);
  }
  vi cnt(N);
  rep(i, N) cnt[par[i]]++;
  sort(all(cnt));
  cout << cnt[N - 1] << endl;
  return 0;
}

Submission Info

Judge Result