# 11117: 【原1117】Code

### 题目描述

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

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

## Sample Input 1

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

5 2 5 2 6 2 8

## Sample Input 2

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

2 1 6 2 6

## Restrictions

70%的数据: N<=1000

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

## FineArtz's solution

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

int a[100005], heap[100005];
int degree[100005] = {0};
bool b[100005];
int heapsize = 0, n = 0, cnt = 0;

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
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){
}
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 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;
}