백준 20531번: 인간관계 [C++]

작성일 | In
플래티넘 V 플래티넘 V

문제

인간관계

풀이

$dp[i][j]$를 $i$명의 학생을 $j$개의 그룹으로 나누는 경우의 수로 정의합시다. 그렇다면 아래 점화식을 통해 경우의 수를 구할 수 있습니다.

\[dp[i][j] = dp[i - 1][j] \times j + dp[i - 1][j - 1]\]

총 $M$번에 걸쳐 분리 집합에서 학생들을 합쳐줍시다. 만약 합치기 전 두 학생이 다른 그룹에 속해있었다면 총 그룹의 개수는 $1$ 줄어듭니다.

그룹의 개수를 $c$라 하면 출력해야 하는 답은 $\sum dp[c][i]$이므로 미리 누적 합 전처리를 해두고 출력하면 됩니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif
using namespace std;

template <size_t n>
struct DisjointSet {
    int parent[n];

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

    int findParent(int v) {
        if (v != parent[v])
            parent[v] = findParent(parent[v]);
        return parent[v];
    }

    void unionParent(int u, int v) {
        u = findParent(u), v = findParent(v);
        parent[u] = v;
    }

    bool isConnected(int u, int v) { return findParent(u) == findParent(v); }
};
DisjointSet<5050> disjointSet;

long long dp[5050][5050];
long long MOD = 1e9 + 7;

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

    int N, M;
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        dp[i][1] = 1;
        for (int j = 2; j <= N; j++) {
            dp[i][j] = dp[i - 1][j] * j + dp[i - 1][j - 1];
            dp[i][j] %= MOD;
        }
    }
    for (int i = 1; i <= N; i++) {
        for (int j = 2; j <= N; j++) {
            dp[i][j] += dp[i][j - 1];
            dp[i][j] %= MOD;
        }
    }

    int components = N;
    while (M--) {
        int x, y;
        cin >> x >> y;

        if (not disjointSet.isConnected(x, y))
            components--;
        disjointSet.unionParent(x, y);

        cout << dp[components][components] << '\n';
    }

    return 0;
}

백준 20531번: 인간관계 [C++]