poj2567 code the tree

一棵树 (也就是一个连通无回路图)，树的结点用整数1, …, N编号。 树的Prufer码构造如下：取具有最小编号的树叶（仅和一条边关联的顶点），将该树叶和它所关联的边从图中删除，并记下关联于该树叶的结点的编号。在获取的图中重复这一过程，直到只留下一个结点。显然，这个唯一留下的顶点编号为N。被记下的N−1个数的序列被称为树的Prufer码。

给出一棵树，计算其Prufer码。树表示如下：

T ::= "(" N S ")"

S ::= " " T S | empty

N ::= number

即，树用括号把它们括起来，用数字表示其根节点的标识符，后面跟用一个空格分开的任意多的子树（也可能没有）。下图中的树是样例输入中的第一行给出的测试用例。

http://poj.org/images/2567_1.jpg

要注意的是，按上述定义，树的根也可能是树叶。这仅用于我们指定某个节点为树根的情况。通常，我们这里处理的树被称为“无根树”。

Input

输入包含若干测试用例，每个测试用例一行，按上述的方式描述一棵树。输入以EOF结束。设定1<=n<=50。

Output

对每个测试用例输出树的Prufer码，每个用例一行。数字间用一个空格分开，行结束时不要打印空格。

Sample Input

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

(1 (2 (3)))

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

Sample Output

5 2 5 2 6 2 8

2 3

2 1 6 2 6

code:

#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 7;
int n, root;
vector<int> g[N];
int vis[N], deeep[N], mx, du[N];
int pat[N];
void prufer()
{
    for (int i = 1; i < n - 1; i++)
    {
        int mnid = -1;
        for (int j = 1; j <= n; j++)
        {
            if (du[j] == 1)
            {
                mnid = j;
                break;
            }
        }
        // cout << mnid << " ";
        du[mnid] = 0;
        du[pat[mnid]]--;
        cout << pat[mnid] << " ";
    }
    cout << n << " ";
    cout << '\n';
}
int main()
{
    int yt = 0;
    string s;
    while (getline(cin, s))
    {
        yt++;
        bool fst = false;
        int rt = -1;
        memset(du, 0, sizeof(du));
        memset(pat, 0, sizeof(pat));
        n = -1;

        stack<int> stk;
        stk.push(-1);
        for (int i = 0; i < s.size(); i++)
        {
            char ch = s[i];
            if (ch == '(')
            {
                int k = i + 1;
                int x = 0;
                while (s[k] >= '0' && s[k] <= '9')
                {
                    x *= 10;
                    x += (s[k] - '0');
                    k++;
                }
                stk.push(x);
                n = max(n, x);
                // cout << x;
            }
            if (ch == ')')
            {
                int tp = stk.top();
                stk.pop();
                du[stk.top()]++;
                du[tp]++;
                pat[tp] = stk.top();
                pat[stk.top()] = tp;
                // cout << tp << " " << stk.top() << '\n';
                // cout << stk.top() << ": " << du[stk.top()] << '\n';
                // cout << tp << ": " << du[tp] << '\n';
            }
        }
        if (n == 1)
            continue;
        prufer();
    }

    return 0;
}