BOJ 20531 인간관계

문제 링크입니다.

친구의 친구는 친구

친구의 무리 중 단 한 명이라도 친구가 되면 그 무리 전체와 친구가 됩니다. 그래서 마치 친구 무리를 한 명의 친구인 것처럼 생각해 주어도 좋습니다.

그렇다면 문제는 친구 관계가 새로 생길 때마다, 친구 무리의 수를 세서 그 수만큼의 친구가 있을 때 친구 관계가 형성되는 경우의 수를 구하면 됩니다. 친구 무리의 수를 세는 것은 분리 집합 등의 자료 구조를 이용해 두 무리가 합쳐질 때마다 무리의 수를 1씩 깎는 방식으로 쉽게 할 수 있습니다.

관계 형성

무리의 수가 정해졌다면 그에 해당하는 답을 찾아야 합니다. 귀찮으니까 모든 가능한 무리의 수에 대한 답을 미리 구해둡시다.

각 무리들을 다시 큰 무리로 각각 묶는 방법의 수는 곧 집합의 분할을 구하는 문제가 됩니다. 벨 수라는 이름이 있는 유서 깊은 문제니, 이 점화식을 그대로 써서 답을 구해 줍시다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9+7;

ll d[5050][5050];
int par[5050];
int comp;

int f(int x){
	return par[x] < 0 ? x : par[x] = f(par[x]);
}

void u(int x, int y){
	x = f(x); y = f(y);
	if(x == y) return;
	comp--;
	if(par[x] > par[y]) swap(x, y);
	par[x] += par[y];
	par[y] = x;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);
	memset(par, -1, sizeof(par));
	for(int i = 1; i <= 5000; i++){
		d[i][0] = d[i][1] = 1;
		for(int j = 2; j <= i; j++){
			d[i][j] = (d[i-1][j]*j+d[i-1][j-1])%mod;
			d[i][0] = (d[i][0]+d[i][j])%mod;
		}
	}
	int n, m; cin >> n >> m; comp = n;
	while(m--){
		int x, y; cin >> x >> y;
		u(x, y);
		cout << d[comp][0] << '\n';
	}
}