Skip to content

11117: 【原1117】Code

题目

题目描述

author: Zhiming Zhou 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1117

Description

以如下格式给出一颗树形图:

T: = "(" N S ")"
S: = " " T S
   | empty
N: = number

就是说，一个括号代表一颗子树，括号里的第一个数表示树根，内部嵌了多少个括号表示有多少个儿子。

如：(2 (6 (7)) (3) (5 (1) (4)) (8)) 即表示下图：

Example

每次找到最小叶子节点，输出它的相邻节点（叶子节点只有一个相邻节点），删除该叶子节点。循环对图做这个操作，直到只剩一个节点。最后一共要输出N-1个数。

Input Format

一行，表示一颗树形图。

Output Format

一行，若干个数，用空格隔开。

Sample Input 1

(2 (6 (7)) (3) (5 (1) (4)) (8))

Sample Output 1

5 2 5 2 6 2 8

Sample Input 2

(6 (1 (4)) (2 (3) (5)))

Sample Output 2

2 1 6 2 6

Restrictions

树的节点数N满足:

70%的数据: N<=1000

100%的数据: 2<N<=100000

节点编号为1, 2, ..., N。

内存限制：64MB

时间限制：1000ms

FineArtz's solution 

/* Code */
#include <iostream>
using namespace std;

int a[100005], heap[100005];
int degree[100005] = {0};
bool b[100005];
int head[100005], nxt[200005], prv[200005], e[200005];
int heapsize = 0, n = 0, cnt = 0;

void addEdge(int u, int v){
    nxt[++cnt] = head[u];
    if (head[u] != 0)
        prv[head[u]] = cnt;
    head[u] = cnt;
    e[cnt] = v;
    ++degree[u];
    ++degree[v];
}

void delEdge(int u, int x){
    //cout << e[x] << ' ' << e[prv[x]] << ' ' << e[nxt[x]] << endl;
    if (nxt[x] != 0)
        prv[nxt[x]] = prv[x];
    if (prv[x] != 0)
        nxt[prv[x]] = nxt[x];
    else
        head[u] = nxt[x];
    prv[x] = nxt[x] = 0;
}

void swap(int x, int y){
    int t = heap[x];
    heap[x] = heap[y];
    heap[y] = t;
}

void siftup(){
    int i = heapsize;
    while (i != 1){
        if (heap[i] < heap[i / 2]){
            swap(i, i / 2);
            i /= 2;
        }
        else
            break;
    }
}

void siftdown(){
    int i = 2;
    while (i <= heapsize){
        if (i + 1 <= heapsize && heap[i + 1] < heap[i])
            ++i;
        if (heap[i / 2] > heap[i]){
            swap(i / 2, i);
            i *= 2;
        }
        else
            break;
    }
}

void remove(){
    swap(1, heapsize);
    --heapsize;
    siftdown();
}

void insert(int x){
    heap[++heapsize] = x;
    siftup();
}

void buildTree(int x){
    char ch;
    int num = 0;
    cin >> ch;
    while (isdigit(ch)){
        num = num * 10 + ch - '0';
        cin >> ch;
    }
    if (num > n)
        n = num;
    if (x){
        addEdge(num, x);
        addEdge(x, num);
    }
    a[num] = num;
    while (ch == '('){
        buildTree(num);
        cin >> ch;
    }
}

int main(){
    char ch;
    cin >> ch;
    buildTree(0);
    for (int i = 1; i <= n; ++i){
        if (degree[a[i]] == 2)
            insert(a[i]);
        b[i] = true;
    }
    for (int i = 1; i < n; ++i){
        int t = heap[1];
        cout << e[head[t]] << ' ';
        b[t] = false;
        remove();
        int j = head[t];
        int u = e[j];
        delEdge(t, j);
        if (j % 2)
            delEdge(u, j + 1);
        else
            delEdge(u, j - 1);
        degree[u] -= 2;
        if (degree[u] == 2)
            insert(u);
    }
    return 0;
}

ligongzzz's solution 

#include "iostream"
#include "cstdio"
#include "cstring"
using namespace std;

int stack_data[100009] = { 0 };
int tree_data[100009] = { 0 };
int child_num[100009] = { 0 };
bool visited[100009] = { 0 };

template <class T>
class mVector {
    T** vector_data = nullptr;
    unsigned int size = 0;
    unsigned int capacity = 0;

public:
    //构造函数
    mVector() = default;
    mVector(unsigned int _size) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
    }
    mVector(unsigned int _size, const T& val) :size(_size) {
        capacity = _size * 2;
        vector_data = new T * [capacity] {nullptr};
        for (unsigned int i = 0; i < _size; ++i)
            vector_data[i] = new T(val);
    }
    mVector(const mVector<T> & _vector) :size(_vector.size), capacity(_vector.capacity) {
        vector_data = new T * [capacity] {nullptr};
        for (int i = 0; i < size; ++i)
            vector_data[i] = new T(*_vector.vector_data[i]);
    }
    //析构函数
    ~mVector() {
        for (unsigned int i = 0; i < size; ++i)
            delete vector_data[i];
        delete[] vector_data;
    }

    //迭代器
    class iterator {
        T** pos = nullptr;
        friend iterator mVector<T>::begin();
        friend iterator mVector<T>::end();
        friend void mVector<T>::erase(const iterator& val);
    public:
        iterator() = default;
        iterator(const iterator& other) {
            pos = other.pos;
        }
        iterator& operator++() {
            ++pos;
            return *this;
        }
        iterator operator++(int) {
            iterator temp(*this);
            ++pos;
            return temp;
        }
        iterator& operator--() {
            --pos;
            return *this;
        }
        iterator operator--(int) {
            iterator temp(*this);
            --pos;
            return temp;
        }
        bool operator==(const iterator& other) const {
            return pos == other.pos;
        }
        bool operator!=(const iterator& other) const {
            return pos != other.pos;
        }
        iterator& operator=(const iterator& other) {
            pos = other.pos;
            return *this;
        }
        T& operator*() const {
            return **pos;
        }
    };

    //增加元素
    void push_back(const T & val) {
        if (size < capacity)
            vector_data[size++] = new T(val);
        else {
            T** temp_data = new T * [(capacity + 1) * 2]{ nullptr };
            for (unsigned int i = 0; i < size; ++i)
                temp_data[i] = vector_data[i];
            temp_data[size++] = new T(val);
            capacity = (capacity + 1) * 2;
            delete[] vector_data;
            vector_data = temp_data;
        }
    }

    //删除末尾
    void pop_back() {
        delete vector_data[size - 1];
        vector_data[--size] = nullptr;
    }

    //清空
    void clear() {
        for (unsigned int i = 0; i < size; ++i) {
            delete vector_data[i];
            vector_data[i] = nullptr;
        }
        size = 0;
    }

    //删除
    void erase(const iterator & val) {
        delete* val.pos;
        for (auto p = val.pos; p != vector_data + size - 1; ++p)
            * p = *(p + 1);
        --size;
        vector_data[size] = nullptr;
    }

    //重载运算符
    T & operator[](const unsigned int& pos) {
        return *vector_data[pos];
    }

    iterator begin() {
        iterator temp;
        temp.pos = vector_data;
        return temp;
    }

    iterator end() {
        iterator temp;
        temp.pos = vector_data + size;
        return temp;
    }

};

template <class T>
class myPriorityQueue {
public:
    mVector<T> queueData;
    unsigned int sizeOfQueue = 0;
    bool(*cmp)(T a, T b) = [](T a, T b) {return a < b; };

    //向下过滤
    void percolateDown(unsigned int pos) {
        while (pos * 2 <= sizeOfQueue) {
            if (pos * 2 + 1 > sizeOfQueue) {
                //交换
                if (cmp(queueData[pos * 2], queueData[pos])) {
                    auto temp = queueData[pos * 2];
                    queueData[pos * 2] = queueData[pos];
                    queueData[pos] = temp;
                }
                break;
            }
            else {
                bool minNum = cmp(queueData[pos * 2 + 1], queueData[pos * 2]);
                if (cmp(queueData[pos * 2 + minNum], queueData[pos])) {
                    auto temp = queueData[pos * 2 + minNum];
                    queueData[pos * 2 + minNum] = queueData[pos];
                    queueData[pos] = temp;
                    pos = pos * 2 + minNum;
                }
                else break;
            }
        }
    }


    //构建
    myPriorityQueue() {
        queueData.clear();
        queueData.push_back((T)0);
        sizeOfQueue = 0;
    }

    //compare函数返回父结点a与孩子结点b的关系正确与否
    myPriorityQueue(bool(*compare)(T a, T b)) :cmp(compare) {
        queueData.clear();
        queueData.push_back(*new T);
        sizeOfQueue = 0;
    }

    //根据数组建立堆
    void buildHeap(T* eleData, unsigned int eleNum) {
        queueData.clear();
        sizeOfQueue = eleNum;
        queueData.push_back(*new T);
        for (unsigned int i = 1; i <= eleNum; i++)
            queueData.push_back(eleData[i - 1]);
        //向下过滤
        for (unsigned int pos = eleNum / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    void refresh() {
        //向下过滤
        for (unsigned int pos = size() / 2; pos > 0; pos--)
            percolateDown(pos);
    }

    //判断是否空
    bool empty() {
        return sizeOfQueue == 0;
    }

    //返回队列大小
    auto size() {
        return sizeOfQueue;
    }

    //入队
    void push(const T & input) {
        sizeOfQueue++;
        queueData.push_back(input);

        //向上过滤
        for (auto i = sizeOfQueue; i > 1; i = i / 2) {
            //判断是否比父结点更小
            if (cmp(queueData[i], queueData[i / 2])) {
                //交换
                auto temp = queueData[i];
                queueData[i] = queueData[i / 2];
                queueData[i / 2] = temp;
            }
            else break;
        }
    }

    //队列最前
    T top() {
        return queueData[1];
    }

    //出队
    T pop() {
        auto temp = queueData[1];
        queueData[1] = queueData[sizeOfQueue--];
        queueData.pop_back();
        percolateDown(1);
        return temp;
    }
};

myPriorityQueue<int> leaves;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int stackn = 0;
    char ch_temp;
    cin >> ch_temp;
    int init_temp;
    cin >> init_temp;
    stack_data[stackn++] = init_temp;
    int n = 1;
    while (stackn) {
        char temp_ch;
        cin >> temp_ch;
        if (temp_ch == '(') {
            int temp;
            cin >> temp;
            ++n;
            stack_data[stackn++] = temp;
        }
        else {
            //TODO
            if (stackn > 1)
                tree_data[stack_data[stackn - 1]] = stack_data[stackn - 2];
            stack_data[--stackn] = 0;
        }
    }

    //寻找根节点
    int root;
    for (int i = 1; i <= n; ++i) {
        if (tree_data[i] == 0) {
            root = i;
            break;
        }
    }
    //寻找叶子
    for (int i = 1; i <= n; ++i) {
        if (i != root)
            ++child_num[tree_data[i]];
    }

    for (int i = 1; i <= n; ++i) {
        if (child_num[i] == 0 || (i == root && child_num[i] == 1))
            leaves.push(i);
    }

    for (int cnt = 0; cnt + 1 < n; ++cnt) {
        auto temp = leaves.pop();
        visited[temp] = true;
        --child_num[tree_data[temp]];
        if (temp != root) {
            cout << tree_data[temp] << " ";
            if (!visited[tree_data[temp]] && ((tree_data[temp] == root && 
                child_num[tree_data[temp]] == 1) || child_num[tree_data[temp]] == 0))
                leaves.push(tree_data[temp]);
        }
        else {
            for (int i = 1; i <= n; ++i) {
                if (!visited[i] && tree_data[i] == root) {
                    cout << i << " ";
                    root = i;
                    //判断是否需要入队
                    if (child_num[root] == 1)
                        leaves.push(root);
                    break;
                }
            }
        }

    }

    return 0;
}