[Atcoder] ABC302 :: E - Isolation

set 자료구조를 잘 써야 하는 문제이다.

N개의 노드가 존재하고, 초기 상태는 어떠한 간선도 존재하지 않는다. 그리고 이제부터 Q개의 쿼리를 입력받게 된다.
쿼리의 개수는 2개인데, 1번 쿼리의 경우 간선을 연결하고 2번 쿼리의 경우 특정 노드와 연결된 모든 간선을 끊는 연산을 수행해야 한다. 각 쿼리를 수행할때 마다 어떠한 노드와도 연결되지 않은 노드의 개수를 출력해야 한다.

N, Q <= 300000이므로, 제한이 꽤나 크다. 처음에는 오프라인 쿼리 + 유니온 파인드로 접근했으나, 이 방법으로는 해결할 수 없다. 뒤에서 부터 본다고 해서 연산 횟수가 줄어들지 않기 때문이다.

각 노드를 기준으로 연결된 노드들을 set으로 관리한다고 생각해보자. 그리고 초기에는 모든 노드가 연결되어 있지 않으므로 answer = n으로 선언하고, answer를 출력하기로 하자.

answer가 변하는 순간은 명확하다. 간선을 연결할때 처음으로 간선이 생기는 노드가 있다면? 과 노드와 연결된 모든 간선을 끊는 경우이다.
이 두가지 케이스를 set으로 쉽게 관리할 수 있고, 이 경계선에 조건문을 걸어 answer를 업데이트하면 된다. 

시간복잡도는 쿼리별로 set을 조회하기 때문에 O(QlogN)로 잡을 수 있다.

 

#include<iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
using namespace std;
int n, m;
set<int> v[300010];

int main()
{
    cin >> n >> m;
    int answer = n;
    for (int i=0; i<m; i++) {
        int x, y, z;
        cin >> x;
        if (x == 1) {
            cin >> y >> z;
            if (v[y].size() == 0) {
                answer--;
            }
            if (v[z].size() == 0 ) {
                answer--;
            }
            v[y].insert(z);
            v[z].insert(y);
            
        } 
        else {
            cin >> y;        
            for (auto next : v[y]) {
                v[next].erase(y);
                if (v[next].size() == 0) answer++;
            }
            if (v[y].size() > 0 ) answer++;
            v[y].clear();
        }
        cout << answer << '\n';
    }
    return 0;
}