BOJ 21932 To be Connected, or not to be, that is the Question

📝 문제 정보

#

• 링크: https://www.acmicpc.net/problem/21932
• 번역

문제 번역

#

문제 설명

#

무방향 그래프가 주어지고, 각 노드에는 양의 정수 값이 연결되어 있습니다. 임계값(threshold)이 주어지면, 그래프의 노드들은 두 그룹으로 나뉩니다: 하나는 임계값 이하의 값을 가진 노드들로 구성되고, 다른 하나는 나머지 노드들로 구성됩니다. 이제 서로 다른 그룹에 속한 두 노드를 연결하는 모든 간선을 제거하여 얻은 원래 그래프의 부분 그래프를 고려합니다. 두 노드 그룹이 모두 비어있지 않을 때, 주어진 그래프가 연결되어 있는지 여부와 관계없이 결과 부분 그래프는 연결이 끊어집니다.

그런 다음 부분 그래프를 연결되게 만들기 위해 여러 개의 새로운 간선이 추가되지만, 이 간선들은 반드시 서로 다른 그룹의 노드들을 연결해야 하며, 각 노드는 최대 하나의 새로운 간선과만 연결될 수 있습니다. 임계값이 실행 가능(feasible) 하다는 것은 두 그룹 모두 비어있지 않고, 새로운 간선들을 추가하여 부분 그래프를 연결되게 만들 수 있다는 의미입니다.

여러분의 과제는 최소 실행 가능 임계값을 찾는 것입니다.

입력

#

입력은 다음 형식의 단일 테스트 케이스로 구성됩니다.

n m
l1 . . . ln
x1 y1
.
.
.
xm ym

첫 번째 줄에는 두 정수 $n (2 ≤ n ≤ 10⁵)$과 $m (0 ≤ m ≤ min(10⁵, n(n−1)/2))$이 주어지며, 각각 그래프의 노드 개수와 간선 개수를 나타냅니다. 노드는 1부터 n까지 번호가 매겨집니다. 두 번째 줄에는 $n$개의 정수 $l_i (1 ≤ l_i ≤ 10⁹)$가 주어지며, 노드 $i$에 연결된 값이 $l_i$임을 의미합니다. 이후 $m$개의 줄 각각에는 두 정수 $x_j$와 $y_j$ $(1 ≤ x_j < y_j ≤ n)$가 주어지며, 노드 $x_j$와 $y_j$를 연결하는 간선이 있음을 의미합니다. 임의의 두 노드 사이에는 최대 하나의 간선만 존재합니다.

출력

#

최소 실행 가능 임계값을 출력합니다. 실행 가능한 임계값이 없으면 -1을 출력합니다.

🧐 관찰 및 접근

#

• 가중치 기준으로 왼/오 두 그룹으로 나눴을때, 분리집합의 수가 맞아야한다!
  • 단조성이 있다면 매개변수 탐색으로..
    • 정점 수 자체는 단조성이 있지만, 분리집합의 수가 단조성이 없다.
• 전체를 선형으로 하기 위해선, 잘 롤백하면서 하면 되지 않을까?
  • 이제 묶는것 자체는 끝났는데, 어떨 때 연결 할 수 있을까?
• 트리를 생각해보자. 노드 $N$개를 연결하기 위해선 간선이 최소 $N-1$개 필요하다.
  • 우리 상황에서도 간선을 $N-1$개 이상 연결해야하고, $A, B$ 그룹 각각에서 연결 할 수 있는 간선의 수는 $\text{min}(A, B)$이다.
  • 따라서 $C_A + C_B - 1 \leq \text{min}(A, B)$라면 하나로 연결할 수 있다.

💻 풀이

#

• 코드 (C++):

void solve(){
    cin >> N >> M;
    rep(i, 0, N) cin >> W[i];
    rep(i, 0, M){
        int u, v; cin >> u >> v; u--; v--;
        if(W[u] > W[v]) swap(u, v); // now W[u] <= W[v]
        links[v].push_back(u);
        links2[u].push_back(v);
    }

    // compress
    vector<int> ws;
    rep(i, 0, N) ws.push_back(W[i]);
    sort(all(ws));
    ws.erase(unique(all(ws)), ws.end());
    vector<vector<int>> nodes(ws.size());
    rep(i, 0, N){
        int idx = lower_bound(all(ws), W[i]) - ws.begin();
        nodes[idx].push_back(i);
    }
    vector<int> pfsum(ws.size(), 0);
    pfsum[0] = (int)nodes[0].size();
    rep(i, 1, ws.size()) pfsum[i] = pfsum[i-1] + (int)nodes[i].size();
    if(ws.size() == 1){
        cout << -1;
        return;
    }
    
    UnionFind UF1(N), UF2(N);
    rrep(idx, ws.size(), 0){
        for(auto u: nodes[idx]) for(auto v: links2[u]) UF2.merge(u, v);
    }
    rep(idx, 0, ws.size()-1){
        for(auto u: nodes[idx]) for(auto v: links[u]) UF1.merge(u, v);
        for(auto u: nodes[idx]) UF2.rollback((int)links2[u].size());
        if(((pfsum[idx] - UF1.connected) + (N - pfsum[idx] - UF2.connected)) - 1 <= min(pfsum[idx], N - pfsum[idx])){
            cout << ws[idx];
            return;
        }
    }
    cout << -1;
}