취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26077번 문제인 서커스 나이트이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26077 

어떤 두 ID x와 y 사이에 공통 소인수 p가 있다면 x또는 y의 소인수를 가지고 있는 수는 x와 y 둘과 항상 의사소통할 수 있음을 관찰하자. 이를 이용하면 주어진 문제는 각 ID를 노드로, 공통된 소인수를 가지고 있는 두 ID 사이의 관계를 에지로 갖는 그래프에서의 connected component의 크기의 최댓값을 구하는 문제로 바꿔 생각할 수 있게 된다.

위의 그래프에서 모든 두 ID값의 관계를 고려하는 각 ID의 1이 아닌 가장 작은 소인수를 대표값으로 이용하면 그래프의 연결관계는 유지하면서 전체 에지의 수를 크게 줄일 수 있다. 이 관찰과 disjoint set을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <utility>
using namespace std;

int sieve[1000001];

void sieve_init() {
	for (int i = 2; i < 1000; i++) {
		if (sieve[i]) continue;
		sieve[i] = i;
		for (int j = i * i; j < 1000001; j += i) {
			if (sieve[j]) continue;
			sieve[j] = i;
		}
	}
	for (int i = 1000; i < 1000001; i++) {
		if (!sieve[i]) sieve[i] = i;
	}
}

int N;
int arr[1000001];
int cnt[1000001];

int findf(int cur) {
	if (arr[cur] == cur) return cur;
	return arr[cur] = findf(arr[cur]);
}

int ans;

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

	sieve_init();

	for (int i = 1; i < 1000001; i++) arr[i] = i;

	cin >> N;
	while (N--) {
		int x; cin >> x;
		vector<int> factors;
		factors.emplace_back(sieve[x]);
		x /= sieve[x];
		while (x > 1) {
			if (sieve[x] > factors.back()) factors.emplace_back(sieve[x]);;
			x /= sieve[x];
		}

		int fsize = factors.size();
		int L = factors[0]; L = findf(L);
		for (int i = 1; i < fsize; i++) {
			int R = factors[i];
			R = findf(R);
			if (L != R) {
				cnt[L] += cnt[R];
				arr[R] = L;
			}
		}
		cnt[L]++;
	}

	for (int i = 2; i < 1000001; i++) ans = max(ans, cnt[i]);

	cout << ans;
}