拓扑排序 优先级队列 boj1485修改顺序

修改顺序Submit: 462   Accepted:96Time Limit: 10000MS  Memory Limit: 65536KDescription
    champ最近在修改一个游戏，他希望通过修改得到一个拥有全属性、全装备、全物品……的存档。
    经过champ初步统计，它需要修改N个数据才能达到目的。(数据编号从1到N)
    由于游戏本身采取了一些反作弊措施，有时会将用Ai数据去恢复Bi数据。所以champ修改数据时必须先修改Ai然后再修改Bi，以防止程序出错或崩溃。
    现在，champ采集了充足的数据，希望你给他一个修改数据的顺序，正确安全的修改数据。注意，champ的n个数据都要修改。


Input
    多组数据测试
    每组数据第一行两个数N K(N<100000,K<1000000)
    之后K行每行两个数Ai Bi(0     同一组限制不会出现两次
    数据以两个0结束


Output
    每组数据一行，输出可行顺序的最小字典序。可行顺序一定存在。


Sample Input

5 6
1 4
4 3
1 5
5 3
1 3
2 4
0 0


Sample Output

ORDER: 1 2 4 5 3


Hint
    我们可以把n个数据和它们之间的关系抽象成一个图，每个顶点代表一个数据，如果在修改a之前必须修改b,那么a到b之间有一条边a->b。这样，可以抽象成一个有向无环图。
    对应于sample的图

输入输出巨大，请使用scanf，同时输出使用printf。

题意描述：
拓扑排序，并且输出最小字典序的一个可能顺序
采用最小优先级队列可以保证按最小字典序输出

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
using namespace std;

#define SIZE 100010

struct less_cmp
{
    bool operator()(const int &a, const int &b)
    {
        return a > b;
    }
};

vector<int> Vec[SIZE];
priority_queue < int, vector<int>, less_cmp > Que;
int n, k, degree[SIZE];

void clear()
{
    memset(degree, 0, sizeof(degree));
}

int main(int argc, char *argv[])
{
    int i, beg, end;

    while (1)
    {
        scanf("%d %d", &n, &k);
        if (0 == n && 0 == k)
            break;

        for (i=0 ; i<k ; i++)
        {
            scanf("%d %d", &beg, &end);
            Vec[beg].push_back(end);
            degree[end]++;
        }
       


        /* 初始化，将所有入度为0的点加入优先级队列 */
        for (i=1 ; i<=n ; i++)
        {
            if (0 == degree[i])
                Que.push(i);
        }

        int node;
        vector<int>::iterator iter_beg;
        vector<int>::iterator iter_end;
        printf("ORDER:");
        while (!Que.empty())
        {
            node = Que.top();
            Que.pop();
            printf(" %d", node);
            iter_end = Vec[node].end();

            /* 将选出的节点的相邻节点入度减一，如果减后入度为0，入队列 */
            for (iter_beg = Vec[node].begin() ; iter_beg != iter_end ; iter_beg++)
            {
                degree[*iter_beg]--;
                if (0 == degree[*iter_beg])
                    Que.push(*iter_beg);
            }
            Vec[node].clear();
        }
        printf("\n");

        clear();
    }
}

如何去理解 拓扑排序算法

查看Castle的代码，在Castle.Core中内部的数据结构采用图，排序使用的拓扑排序算法：
       对于一条有向边(u,v)，定义u < v；满足所有这样条件的结点序列称为拓扑序列。拓扑排序就是求一个有向图的拓扑序列的算法。
一个有向图顶点的拓扑序列不是惟一的。并不是任何有向图的顶点都可以排成拓扑序列，有环图是不能排的。
例子：比如排课问题，比如士兵排队问题等。
       拓扑排序在实际生活中和算法中都有很大的应用。比如要排一下几门课程的先后次序，我们可以把课程抽象成结点，把什么课是什么课的基础抽象成边，那么该图的一个拓扑序列就是这些课的一个可行的先后次序。各种语言的编译器都用到了拓扑排序。
    数学基础：
    什么是拓扑排序(Topological Sort)?简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
    回顾离散数学中关于偏序和全序的定义：
        若集合X上的关系R是自反的、反对称的和传递的，则称只是集合X上的偏序关系。
        设R是集合X上的偏序(Partial Order)，如果对每个x,y∈X必有xRy或yRx，则称R是集合X上的全序关系。
    直观地看，偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间均可比较。[例如]，图7.25所示的两个有向图，图中弧(x,y)表示 x≤y，则(a)表示偏序，(b)表示全序。若在(a)的有向图上人为地加一个表示v2≤v3的弧(符号“≤”表示v2领先于v3)，则(a)表示的亦为 全序，且这个全序称为拓扑有序(Topological Order)，而由偏序定义得到拓扑有序的操作便是拓扑排序。

      
AOV-网及其拓扑有序序列产生的过程
(a)AOV-网；(b)输出v6之后；(c)输出v1之后；(d)输出v4之后；(e)输出v3之后；(f)输出v2之后

    [思想]：
    一、从有向图中选取一个没有前驱的顶点，并输出之；
    二、从有向图中删去此顶点以及所有以它为尾的弧；
    重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱 -- 入度为零，删除顶点及以它为尾的弧-- 弧头顶点的入度减1。

    [人度为零的顶点拓扑排序算法]：
    Status Topological Sort(ALGraph G){
    //有向图G采用邻接表存储结构。
    //若G无回路，则输出G的顶点的1个拓扑序列并返回OK，否则ERROR。
        FindInDegree(G，indegree)； //对各顶点求入度indegree[0..vernum-1]
        InitStack(S)；
        for(i=0；i        if(!indegree[i])Push(S，i) //建零入度顶点栈,s入度为0者进栈
        count=0； //对输出顶点计数
        while (!StackEmpty(S)) {
            Pop(S，i)；
            printf(i，G.vertices[i].data)； ++count； //输出i号顶点并计数
            for(p=G.vertices[i].firstarc；p； p=p—>nextarc) {
                k=p—>adivex； //对i号顶点的每个邻接点的入度减1
                if(！(--indegree[k]))Push(S，k)；//若入度减为0，则入栈
            }//for
        }//while
        if(count        else return OK；
    }//TopologicalSort 
   算法 ，总的时间复杂度为O(n+e)。