题解 CF1131F 【Asya And Kittens】

LJC00118 · 2019-03-01 14:33:16 · 题解

两个被合并的点的联通块一定在序列里是挨着的，直接链表合并，最后遍历一下链表即可

#include <bits/stdc++.h>
#define Fast_cin ios::sync_with_stdio(false), cin.tie(0);
#define rep(i, a, b) for(register int i = a; i <= b; i++)
#define per(i, a, b) for(register int i = a; i >= b; i--)
#define DEBUG(x) cerr << "DEBUG" << x << " >>> " << endl;
using namespace std;

typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef long long ll;

template <typename _T>
inline void read(_T &f) {
    f = 0; _T fu = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') fu = -1; c = getchar(); }
    while(c >= '0' && c <= '9') { f = (f << 3) + (f << 1) + (c & 15); c = getchar(); }
    f *= fu;
}

template <typename T>
void print(T x) {
    if(x < 0) putchar('-'), x = -x;
    if(x < 10) putchar(x + 48);
    else print(x / 10), putchar(x % 10 + 48);
}

template <typename T>
void print(T x, char t) {
    print(x); putchar(t);
}

template <typename T>
struct hash_map_t {
    vector <T> v, val, nxt;
    vector <int> head;
    int mod, tot, lastv;
    T lastans;
    bool have_ans;

    hash_map_t (int md = 0) {
        head.clear(); v.clear(); val.clear(); nxt.clear(); tot = 0; mod = md;
        nxt.resize(1); v.resize(1); val.resize(1); head.resize(mod);
        have_ans = 0;
    }

    bool count(int x) {
        int u = x % mod;
        for(register int i = head[u]; i; i = nxt[i]) {
            if(v[i] == x) {
                have_ans = 1;
                lastv = x;
                lastans = val[i];
                return 1;
            }
        }
        return 0;
    }

    void ins(int x, int y) {
        int u = x % mod;
        nxt.push_back(head[u]); head[u] = ++tot;
        v.push_back(x); val.push_back(y);
    }

    int qry(int x) {
        if(have_ans && lastv == x) return lastans;
        count(x);
        return lastans;
    }
};

const int N = 150005;

int f[N], head[N], tail[N], nxt[N];
int n;

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

int main() {
    read(n);
    for(register int i = 1; i <= n; i++) {
        f[i] = i;
        head[i] = tail[i] = i;
    }
    for(register int i = 1; i < n; i++) {
        int a, b; read(a); read(b);
        int x = find(a), y = find(b); f[y] = x;
        nxt[tail[x]] = head[y];
        tail[x] = tail[y];
    }
    int u = find(1);
    for(int i = head[u]; ; i = nxt[i]) {
        printf("%d ", i);
        if(i == tail[u]) break;
    }
    putchar('\n');
    return 0;
}