백준1376 민식 우선 탐색

작성일 | In

문제 링크

  • http://icpc.me/1376

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(N log N)$

풀이

각 정점마다, 인접한 정점 중 아직 방문하지 않은 정점을 세그먼트 트리로 관리해줍시다.
갈 수 있는 정점의 개수, 갈 수 있는 정점 중 번호가 가장 작은 정점, 중간값인 정점을 모두 구해줄 수 있습니다.

현재 구간에 있는 원소의 개수, K번째 원소를 찾는 쿼리와 임의의 원소를 제거하는 쿼리를 지원하는 세그먼트 트리를 열심히 구현해주면 됩니다.
Self Loop와 Multi Edge에 대한 예외처리가 필요합니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;
typedef pair<int, int> p;

int n, m;
vector<p> edge;
vector<int> g[101010];

struct Seg{
    int cnt, sz;
    vector<int> tree, mx;
    void init(int v){
        sz = 2; cnt = g[v].size();
        while(sz < cnt*2) sz <<= 1;
        tree.resize(sz); mx.resize(sz); sz >>= 1;
        for(int i=0; i<cnt; i++) tree[i|sz] = 1, mx[i|sz] = g[v][i];
        for(int i=sz-1; i; i--){
            tree[i] = tree[i << 1] + tree[i << 1 | 1];
            mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
        }
    }
    int even(){
        int node = 1;
        while(node < sz){
            if(tree[node << 1]) node = node * 2;
            else node = node * 2 + 1;
        }
        return mx[node];
    }
    int odd(){
        int node = 1, k = (tree[1] + 1) / 2;
        while(node < sz){
            if(tree[node << 1] >= k) node = node * 2;
            else k -= tree[node << 1], node = node * 2 + 1;
        }
        return mx[node];
    }
    int query(){
        if(tree[1] & 1) return odd();
        return even();
    }
    void erase(int x){
        int node = 1;
        while(node < sz){
            if(mx[node << 1] >= x) node = node * 2;
            else node = node * 2 + 1;
        }
        if(mx[node] != x) return;
        x = node;
        tree[x] = mx[x] = 0;
        while(x >>= 1){
            tree[x] = tree[x << 1] + tree[x << 1 | 1];
            mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
        }
    }
} seg[101010];

int chk[101010];

void dfs(int v){
    chk[v] = 1;
    cout << v << " ";
    while(1){
        int t = seg[v].query();
        if(!t) break;
        for(auto i : g[t]) seg[i].erase(t);
        dfs(t);
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> m;
    for(int i=0; i<m; i++){
        int s, e; cin >> s >> e;
        if(s == e) continue;
        if(s > e) swap(s, e);
        edge.emplace_back(s, e);
    }
    compress(edge);
    for(auto i : edge) g[i.x].push_back(i.y), g[i.y].push_back(i.x);
    for(int i=1; i<=n; i++) sort(all(g[i]));
    for(int i=1; i<=n; i++) seg[i].init(i);

    for(auto i : g[1]) seg[i].erase(1);
    dfs(1);
}