zoj 1097 普吕弗序列

题目大意：输入一颗无根树的括号序列，求这棵树的普吕弗序列。

分析思路：

1）普吕弗序列，可以参考维基百科，其做法是找出树中编号最小的叶子节点，并将此叶子节点及边删除，并输出其邻接的节点标号；

2）递归地构造树，可以使用list<int> 数组来表示一个“邻接表”，以存储构造的树；

3）使用优先队列来进行删除，奈何priority_queue没有迭代器访问，只能用堆排序，取最值；

代码：

#include<iostream>

#include<vector>

#include<map>

#include<queue>

#include<string>

#include<algorithm>

#include<fstream>

#include<list>

using namespace std;

struct nodeAndDegree

{

    int degree;      //度

    int nodeNumber;  //结点编号

    bool operator < (const nodeAndDegree& n1)const

    {

        return  degree == n1.degree ? (nodeNumber > n1.nodeNumber) : (degree > n1.degree);

    }

};

const int MAX_LEN = 55;

list<int> vGraph[MAX_LEN];

vector<int> v;

int rootNumber = 0;

void dfs(int start, int end, int parent, string str)

{

    if (start == end)  //只有单个点

    {

        return;

    }

    //放入邻接矩阵

    int currentNode = 0;

    for (int i = start + 1; i <= end - 1; i++)

    {

        if (str[i] == ' ' || str[i] == '\0' || str[i] == '(')

        {

            break;

        }

        currentNode = currentNode * 10 + (int)(str[i] - 48);

    }

    //放入邻接矩阵

    vGraph[parent].push_back(currentNode);

    vGraph[currentNode].push_back(parent);

    v.push_back(currentNode);

    int mark = 0;

    int tmpStart = -1;

    for (int i = start + 1; i <= end - 1; i++)

    {

        if (str[i] == '(')

        {

            mark++;

            if (tmpStart == -1) tmpStart = i;

            continue;

        }

        if (str[i] == ')')

        {

            mark--;

            if (mark == 0)

            {

                dfs(tmpStart, i, currentNode, str);

                tmpStart = -1;

            }

        }

    }

}

void print_prufer_sequnce()

{

    //首先修改根节点对应的长度

    int tmp = vGraph[0].front();

    vGraph[tmp].remove(0);

    vector<nodeAndDegree> listNodeDegree;

    for (int i = 0; i < v.size(); i++)

    {

        nodeAndDegree *nd = new nodeAndDegree();

        nd->nodeNumber = v[i];

        nd->degree = vGraph[v[i]].size();

        listNodeDegree.push_back(*nd);

    }

    int n = v.size() - 1;

    int index = 0;

    while (index < n)

    {

        make_heap(listNodeDegree.begin(), listNodeDegree.end());

        int number = listNodeDegree[0].nodeNumber;  //当前结点

        int front = vGraph[number].front();

        cout << front ;

        if (index != n - 1)

        {

            cout << " ";

        }

        vGraph[front].remove(number);

        vGraph[number].remove(front);

        for (int j = 1; j < listNodeDegree.size(); j++)

        {

            if (listNodeDegree[j].nodeNumber == front)

            {

                listNodeDegree[j].degree--;

                break;

            }

        }

        listNodeDegree.erase(listNodeDegree.begin());

        index++;

    }

}

int main()

{

    string s;

    //fstream cin("1097.txt");

    while (getline(cin, s))

    {

        for (int i = 0; i < MAX_LEN; i++)

        {

            vGraph[i].clear();

        }

        v.clear();

        dfs(0, s.size() - 1, 0, s);

        print_prufer_sequnce();

        cout << endl;

    }

    return 0;

}

以纪念我那逝去的耗费精力的兴奋的AC。

巴特西

zoj 1097 普吕弗序列

最新文章

热门文章