确定比赛

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 10358    Accepted Submission(s): 4046

4 3

1 2

2 3

4 3

1 2 4 3

解题思路：

原理：拓扑排序是应用于有向无回路图（DAG）上的一种排序方式。对一个有向无回路进行拓扑排序后，全部的顶点形成一个序列，对全部边(u,v)，满足u在v的前面。该序列说明了顶点表示的事件或 状态发生的总体顺序。比較经典的是在project活动上，某些project完毕后。还有一些project才干继续，此时能够以project为顶点，project间的依赖关系为边建立图。用拓扑排序来求得全部project的合理运行顺序。

对一个DAG进行拓扑排序有两种方法，广度优先搜索和深度优先搜索。

这里介绍广度优先搜索。进行拓扑排序时，每次能够拿出的顶点一定是入度为0的点，即没有被指向的点，由于这种点表示的事件没有依赖。在一个入度为0的点表示的事件运行完之后。它所指向的顶点所依赖的点就少了一个。所以我们能够先将全部入度为0的点增加一个队列中。然后依次将它们所指向的点的入度减1，再将入度变为0的点也依次增加队列中。这样最后就能够得到一个拓扑有序的序列。

本题中说符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前。须要用到优先队列，每次从队列中取的是最小的那个元素。

代码：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <queue>

using namespace std;

const int maxn=510;

int graph[maxn][maxn];//保存图

int degree[maxn];//保存入度

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        memset(graph,0,sizeof(graph));

        memset(degree,0,sizeof(degree));

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

        {

            int u,v;

            scanf("%d%d",&u,&v);

            if(!graph[u][v])

            {

                graph[u][v]=1;

                degree[v]++;//v的入度++

            }

        }

        priority_queue<int,vector<int>,greater<int> >q;

        for(int i=1;i<=n;i++)

            if(degree[i]==0)

            q.push(i);

        bool first=1;

        while(!q.empty())

        {

            int cur=q.top();

            q.pop();

            if(first)

            {

                cout<<cur;

                first=0;

            }

            else

                cout<<" "<<cur;

            for(int i=1;i<=n;i++)

            {

                if(graph[cur][i])

                {

                    degree[i]--;//相连的点的入度减1

                    if(degree[i]==0)//假设入度为0，增加队列

                        q.push(i);

                }

            }

        }

        printf("\n");

    }

    return 0;

}