[Algorithm] C++ 백준 16041번 : Double Clique

아이디어 요약

Double Clique란 S가 G에서 클릭이고, V−S가 G'(보수 그래프)에서 클릭인 부분집합입니다. 이는 원래 그래프 G에서 S는 클릭, T=V−S는 독립 집합이 되는 스플릿(split) 그래프 분할을 의미합니다.
정점 차수를 내림차순으로 정렬하고 상위 s개의 차수 합을 sum_S라 하면, 스플릿 분할의 필요충분식은 sum_S − s(s−1) = 2m − sum_S 입니다.
- 좌변은 S와 T 사이 간선 수 X, 우변은 전체 차수합 2m에서 S의 차수합을 뺀 sum_T = X와 동일해야 합니다.
위 등식이 처음 성립하는 s를 찾아 분할 (S,T)를 결정합니다. 이후 경우의 수는 다음 세 가지를 모두 더합니다.
1. 기본 집합 S 자체.
2. S 내부에서 차수가 정확히 s−1인 정점 x를 제거해도 T에 간선이 없어 S\\{x}가 유효.
3. T에서 차수가 정확히 s인 정점 y를 추가하여 S∪{y}가 유효. 또한 이런 y와 S 내부에서 차수 s인 정점 x를 교환해도 유효(S∪{y}\\{x}).
총합을 1e9+7로 모듈러 하여 출력합니다. 인접 리스트는 필요 없고 차수만 있으면 됩니다.

C++ 풀이

 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
// 42jerrykim.github.io에서 더 많은 정보를 확인 할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;

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

    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<int> deg(n, 0);
    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        --a; --b;
        deg[a]++; deg[b]++;
    }

    vector<pair<int,int>> v(n);
    for (int i = 0; i < n; ++i) v[i] = {deg[i], i};
    sort(v.begin(), v.end(), [](const auto& x, const auto& y){
        if (x.first != y.first) return x.first > y.first;
        return x.second < y.second;
    });

    const long long MOD = 1000000007LL;
    long long tot2 = 2LL * m;
    long long sum = 0;
    vector<long long> freq(n + 1, 0); // freq[d]: # of vertices in S with degree d
    int size = -1;

    for (int i = 0; i < n; ++i) {
        long long s = i + 1;
        if (tot2 - s * (s - 1) < 0) break; // early impossibility
        sum += v[i].first;
        int d = v[i].first;
        if (d <= n) freq[d]++;

        long long rest = sum - s * (s - 1); // edges between S and T
        if (rest == tot2 - sum) {          // T has no internal edges
            size = (int)s;
            break;
        }
    }

    if (size == -1) {
        cout << 0 << '\n';
        return 0;
    }

    long long res = 1; // base set S
    for (int i = 0; i < size; ++i) {
        if (deg[v[i].second] == size - 1) {
            res++;
            if (res >= MOD) res -= MOD;
        }
    }
    for (int i = size; i < n; ++i) {
        if (deg[v[i].second] == size) {
            res++; if (res >= MOD) res -= MOD;     // add this vertex to S
            res = (res + freq[size]) % MOD;        // swap with any vertex in S of degree == size
        }
    }

    cout << (res % MOD) << '\n';
    return 0;
}