백준 26971, Strongest Friendship Group

 

 

 

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

26971번: Strongest Friendship Group

요약

 

 

그래프에서 (sub graph의 크기) * (sub graph 내부의 정점의 최소 degree) 의 최대를 구하여라.

---

1. 정점의 개수 N과 간선의 개수 M이 주어진다. 이때, 주어진 그래프의 모든 부분그래프들 중, (sub graph의 크기)와 (그 내부 정점의 최소 degree)의 곱의 최대를 구해야 한다. 이때, degree를 구할 때는 같은 sub graph 내부에 있는 정점과의 간선일 때만 세어주어야 한다.

 

2. 전체 그래프에서 가장 degree가 작은 정점 k부터 살펴보자. 만약 답이 되는 sub graph에 k가 포함되어 있다면, 그 답은 (k의 degree) * (k의 connected component의 개수)가 될 것이다. degree가 가장 작은 정점부터 보기 때문에, k의 connected component에서 더 degree가 작은 정점이 있을 수는 없다.

 

3. 가장 작은 정점 k를 살펴보았다면 정점 k를 삭제하고 degree의 변화를 반영한 뒤, 그 다음으로 degree가 작은 정점을 살펴보는 식으로 모든 정답의 후보를 파악할 수 있다. 이러한 구현은 정점 삭제가 O(N + M), sub graph의 크기를 구하는 것에 각 단계마다 O(NM)으로 제한 안에 수행할 수 없다.

 

4. sub graph의 크기를 O(1)에 구하는 자료 구조로 disjoint set을 떠올릴 수 있다. disjoint set은 원소의 삭제가 불편하므로, 원래 순서를 구한 뒤 그 역순으로 정점을 서로 합쳐주는 방식을 통해 구현하도록 하자.

 

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

int N, M;
vector<int> graph[100005];
int parent[100005], sz[100005], degree[100005], mark[100005];
vector<pii> v;

int find(int a) {
    if (a == parent[a]) return parent[a];
    else return parent[a] = find(parent[a]);
}

void merge(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (a > b) {
        parent[a] = b;
        sz[b] += sz[a];
    } else {
        parent[b] = a;
        sz[a] += sz[b];
    }
    return;
}

void solve() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        parent[i] = i;
        sz[i] = 1;
    }

    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        degree[a]++;
        degree[b]++;
    }

    set<pii> s;
    for (int i = 1; i <= N; i++) s.insert({degree[i], i});

    for (int i = 1; i <= N; i++) {
        pii now = *s.begin();
        v.push_back(now);
        s.erase(now);
        mark[now.second] = 1;

        for (int next: graph[now.second]) {
            if (mark[next]) continue;
            s.erase({degree[next], next});
            degree[next]--;
            s.insert({degree[next], next});
        }
    }

    reverse(v.begin(), v.end());
    ll ans = 1;

    memset(mark, 0, sizeof(mark));

    for (int i = 0; i < v.size(); i++) {
        ll now = v[i].second;
        ll d = v[i].first;
        mark[now] = 1;

        for (int next: graph[now]) if (mark[next]) merge(now, next);
        ans = max(ans, d * sz[find(now)]);
    }

    cout << ans;
    return;
}

int main(void) {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    //cin >> t;
    while (t--) solve();
    return 0;
}