백준 1376 - 민식우선탐색

https://www.acmicpc.net/problem/1376

1376번: 민식우선탐색

[알고리즘 분류]

dfs

segment tree

 

 

 pbds로 풀어보려 했지만, clang으로도 TLE 받고 포기했다.

 

 세그먼트 트리를 사용하는 풀이는 간단한 편이다. k번째 수를 찾는 쿼리는 리프노드부터 시작하여 내려오는 과정으로 해결할 수 있다. mfs를 시행할 때마다 현재 노드 \(now\)와 연결된 노드\(nxt\)들에 대해, \(nxt\rightarrow now\) 간선들을 지워주면 된다. 간선을 지우는 것은, 세그먼트 트리에서 특정 원소를 update하는 과정으로 해결하면 된다.

 

 정답 코드는 다음과 같다.

#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long double;
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
 
//const ld eps = 1e-9;
const ll mod = 1e9 + 7;
const ll inf = 1e9;
 
#define all(v) (v).begin(),(v).end()
#define compress(v) sort(all(v)), (v).erase(unique(all(v)), (v).end())
#define X first
#define Y second
#define endl '\n'
 
 
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define MAX(a, b) a = (((a)<(b))?(b):(a))
#define MIN(a, b) a = (((a)>(b))?(b):(a))
 
 
// end of def
 
int n,md;
vector<int> seg[100001];
vector<int> g[100001];
 
void init(int i, int x, int s, int e){
    if (s == e) {
        seg[i][x] = 1;
        return;
    }
    int m = (s + e) / 2;
    init(i, x * 2, s, m); init(i, x * 2 + 1, m + 1, e);
    seg[i][x] = seg[i][x * 2] + seg[i][x * 2 + 1];
}
 
void upd(int i, int x, int s, int e, int idx){
    if (e < idx || idx < s) return;
    if (idx <= s && e <= idx) {
        seg[i][x] = 0;
        return;
    }
    int m = (s + e) / 2;
    upd(i, x * 2, s, m, idx); upd(i, x * 2 + 1, m + 1, e, idx);
    seg[i][x] = seg[i][x * 2] + seg[i][x * 2 + 1];
}
 
 
 
int qry(int i, int x, int s, int e, int k){
    if (s == e) return s;
    int m = (s + e) / 2;
    if (seg[i][x * 2] >= k)
        return qry(i, x * 2, s, m, k);
    else
        return qry(i, x * 2 + 1, m + 1, e, k - seg[i][x * 2]);
}
 
void deleteEdge(int u, int v){
    int idx = lower_bound(all(g[u]), v) - g[u].begin();
    upd(u, 1, 1, (int)g[u].size(), idx + 1);
}
 
void mfs(int x){
    cout<<x<<" ";
    for (int j: g[x]){
        deleteEdge(j, x);
    }
    while (seg[x][1]){
        int qr;
        if (seg[x][1] & 1) qr = qry(x, 1, 1, g[x].size(), seg[x][1] / 2 + 1);
        else qr = qry(x, 1, 1, g[x].size(), 1);
 
        int i = g[x][qr - 1];
        mfs(i);
    }
}
 
int main() {
    fastio;
    cin>>n>>md;
    for (int i=0;i<md;i++){
        int u,v;cin>>u>>v;
        if (u == v)continue;
        g[u].emplace_back(v);
        g[v].emplace_back(u);
    }
    for (int i=1;i<=n;i++){
        compress(g[i]);
        if (!g[i].empty()) {
            seg[i].resize(g[i].size() * 4);
            init(i, 1, 1, g[i].size());
        }
    }
    mfs(1);
    return 0;
}