Atcoder解いてみた AtCoder Beginner Contest D - Friends

AtCoder Beginner Contest D - Friends

問題はこちら

回答

UnionFindを活用する
最終的に、同じ根のグループの要素数を求め、算出した要素数の最大値が、最小で必要な分割グループ数となる

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>
#include <iomanip>
#include <random>

class UnionFind {
private:
	std::vector<int> parent;
	std::vector<int> rank;
	std::vector<int> groupSize;

public:
	UnionFind(const int n) {
		parent.resize(n);
		rank.resize(n);
		groupSize.resize(n);

		for (int i = 0; i < n; i++) {
			parent[i] = i;
			rank[i] = 1;
			groupSize[i] = 0;
		}
	};

	// 根の取得
	int GetRoot(const int val) {

		// 自分自身が根じゃない
		if (val != parent[val]) {
			parent[val] = GetRoot(parent[val]);
			return parent[val];
		}
		else {
			return val;
		}
	}

	// 同じ根かどうかの判定
	bool IsSame(const int val1, const int val2) {
		return GetRoot(val1) == GetRoot(val2);
	}

	// マージ
	void Merge(const int val1, const int val2) {
		int root1 = GetRoot(val1);
		int root2 = GetRoot(val2);

		// 根が同じであれば、マージは必要ない
		if (root1 == root2) {
			return;
		}

		if (rank[root1] > rank[root2]) {
			parent[root2] = root1;
		}
		else {
			parent[root1] = root2;

			if (rank[root1] == rank[root2]) {
				rank[root2]++;
			}
		}

		return;
	}

	int GetMaxGroupNum() {
		for (int i = 0; i < parent.size(); i++) {
			groupSize[i] = 0;
		}

		for (int i = 0; i < parent.size(); i++) {
			groupSize[GetRoot(i)]++;
		}

		std::sort(groupSize.begin(), groupSize.end(), std::greater<int>());

		return groupSize[0];
	}
	
};


int N, M;
std::vector<int> A;
std::vector<int> B;


int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N >> M;

	UnionFind uf(N);

	for (int m = 0; m < M; m++) {
		int a, b;
		std::cin >> a >> b;
		a--;
		b--;

		uf.Merge(a, b);
	}

	std::cout << uf.GetMaxGroupNum() << std::endl;

	return 0;
}

以下のように、マージと同時に、グループの要素数の算出も行った方がいい

void Merge(const int val1, const int val2) {
		int root1 = GetRoot(val1);
		int root2 = GetRoot(val2);

		// 根が同じであれば、マージは必要ない
		if (root1 == root2) {
			return;
		}

		// ランクに基づく結合と、サイズの合流
		if (rank[root1] > rank[root2]) {
			root[root2] = root1;
			groupSize[root1] += groupSize[root2]; // サイズを足し合わせる
		}
		else {
			root[root1] = root2;
			groupSize[root2] += groupSize[root1]; // サイズを足し合わせる

			if (rank[root1] == rank[root2]) {
				rank[root2]++;
			}
		}
	}