백준 28092 우선순위와 쿼리

https://boj.ma/28092/t 

28092번: 우선순위와 쿼리

 

 

초기에 1 ~ N 까지 N개의 정점이 주어지고

2가지 쿼리가 주어집니다.

 

1. u, v사이에 간선을 만드는 쿼리

2. 존재하는 트리 중에 사이즈가 제일 큰 트리에 속한 가장 작은 노드번호 출력 후 트리 삭제(사이즈가 같다면 노드번호가 더 작은 트리)

 

또한 사이클이 존재하면 트리가 아니기때문에 사이즈가 아무리 커도 출력하면 안됩니다.

 

N 이 10만

쿼리도 10만번 까지 가능하기 때문에

매번 간선을 만들고, 모든 정점을 탐색하여 사이즈를 찾고, 제일 사이즈가 큰 트리와 그때 트리에서 가장 작은 노드 번호를 출력하는 것은

시간초과입니다.

 

간선을 만들고 특정 노드가 속한 트리의 사이즈, 그리고 거기서 가장 작은 노드 번호를 구하는 것은

유니온 파인드로 최적화가 가능합니다.

 

2번 쿼리마다 사이즈가 큰 트리와 노드 번호를 출력해야 하는데 유니온 파인드를 통해 잘 저장해놨다 쳐도 이것을 매번 구하기 위해 정렬하고 삭제하는 것은 오래걸리니 pq를 사용했습니다.

삭제연산은 실제로 pq의 모든 원소를 살펴보며 삭제하지 않고, 삭제되었다고 표시하는 배열을 사용해 lazy하게 처리했습니다.

 

code(c++)

#include <bits/stdc++.h>
#define endl "\n"
#define NM 201010
#define MAX 1010100
#define BIAS 100000
#define MOD 1000000007
#define X first
#define Y second
#define INF 0x3f3f3f3f
#define LINF 0x3f3f3f3f3f3f3f3f
#define FOR(i) for(int _=0;_<(i);_++)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;

struct node{
    int sz, num;
};

struct compare{
    bool operator()(const node &a, const node &b){
        if (a.sz != b.sz){
            return a.sz < b.sz;
        }
        return a.num > b.num;
    }
};

priority_queue<node, vector<node>, compare> pq;
int n, q, parent[101010], del[101010], sz[101010];

int find(int x){
    return parent[x] == x ? x : parent[x] = find(parent[x]);
}

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

void input() {
    cin >> n >> q;
    for (int i = 0 ; i < 101010;i++) {
        parent[i] = i;
        sz[i] = 1;
    }
    for (int i = 1; i <= n; i++){
        pq.push({1, i});
    }
}

void pro() {
    while(q--){
        int oper;
        cin >> oper;
        if (oper&1){ // 간선 만들기
            int x, y;
            cin >> x >> y;
            x = find(x);
            y = find(y);
            if (x != y){ // 다른 연결요소
                if (del[x] || del[y]){ // 둘 중 하나가 사이클에 속한 노드
                    del[x] = 1;
                    del[y] = 1;
                    continue;
                }
                merge(x, y); // 합치고
                pq.push({sz[find(x)], find(x)}); // pq에 넣기
            }else{ // 같은 연결요소 -> 사이클 생김 -> 트리가 아님
                del[find(x)] = 1; // 삭제됐다고 표시
            }
        }else{
            while(1){
                node cur = pq.top();pq.pop();
                int x = find(cur.num);
                if (del[x]) continue; // 삭제처리됐으면 무시
                cout << x << endl;
                del[x] = 1; // 삭제처리
                break;
            }
        }
    }
}

int main() {
    fastio;
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    input();
    pro();
    return 0;
}

 

사이클에 속한 노드와 트리에 속한 노들 연결할 수도 있다는 것을 놓쳐서 많이 틀렸습니다.

 

pq말고 set을 이용해 삽입,삭제 연산을 처리한 풀이도 있는것 같습니다.