백준 1741번 - 반 나누기

 

1741번: 반 나누기

요약

주어진 그래프의 꼭지점을 최대한 많은 그룹으로 나누되, 각 꼭지점은 다른 그룹에 속한 모든 꼭지점과 연결되어 있어야 한다.

 

참고

[1] https://github.com/koosaga/olympiad/blob/master/POI/poi07_biu.cpp

[2] https://www.cnblogs.com/Delostik/archive/2011/08/09/2132463.html

 

풀이

주어진 그래프의 complement 그래프를 (있는 edge는 없애고, 없는 edge는 만든다) connected component로 쪼개는 문제다.

BFS를 쓰면 되는데, 문제는 complement 그래프의 edge가 최대 O(N^2)개라는 점이다.

이때 BFS에서 한 꼭지점의 이웃 꼭지점들을 찾는 과정을 간소화시키기 위해 어느 component에 들어갈지 정해진 꼭지점 번호를 없애주는 테크닉을 사용한다.

[1]은 set + upper_bound를 사용했고, 나는 [1]과 [2]를 섞어 list + two pointer를 사용했다.

 

코드

#include "prelude.h"  // 개인 라이브러리

constexpr int INF = INT_MAX / 2;

using namespace std;

int main() {
    DEFIN2(N, M);
    list<int> li;
    FOR1(i, N) {
        li.push_back(i);
    }
    vector<vector<int>> graph(N + 1);
    LOOP(M) {
        DEFIN2(v, w);
        graph[v].push_back(w);
        graph[w].push_back(v);
    }
    for (auto& e : graph) {
        e.push_back(INF);
        sort(begin(e), end(e));
    }

    auto bfs = [&](int cur) {
        int ret = li.size();
        queue<int> q;
        q.push(cur);
        li.pop_front();

        while (!q.empty()) {
            int e = q.front();
            q.pop();

            auto& nbd = graph[e];
            int l = 0;
            auto it = begin(li);
            while (it != end(li)) {
                if (*it < nbd[l]) {
                    q.push(*it);
                    it = li.erase(it);
                } else if (*it == nbd[l]) {
                    ++it;
                } else {
                    ++l;
                }
            }
        }
        return ret - li.size();
    };

    vector<int> ret;
    while (!li.empty()) {
        ret.push_back(bfs(*begin(li)));
    }
    sort(begin(ret), end(ret));

    COUTLN(ret.size());
    for (auto e : ret) {
        PRINT("{} ", e);
    } LN();

    return 0;
}