题解报告：hdu 1285 确定比赛名次

Problem Description

有N个比赛队（1<=N<=500），编号依次为1，2，3，。。。。，N进行比赛，比赛结束后，裁判委员会要将所有参赛队伍从前往后依次排名，但现在裁判委员会不能直接获得每个队的比赛成绩，只知道每场比赛的结果，即P1赢P2，用P1，P2表示，排名时P1在P2之前。现在请你编程序确定排名。

Input

输入有若干组，每组中的第一行为二个数N（1<=N<=500），M；其中N表示队伍的个数，M表示接着有M行的输入数据。接下来的M行数据中，每行也有两个整数P1，P2表示即P1队赢了P2队。

Output

给出一个符合要求的排名。输出时队伍号之间有空格，最后一名后面没有空格。
其他说明：符合条件的排名可能不是唯一的，此时要求输出时编号小的队伍在前；输入数据保证是正确的，即输入数据确保一定能有一个符合要求的排名。

Sample Input

4 3

1 2

2 3

4 3

Sample Output

1 2 4 3

解题思路：拓扑排序裸题。所谓的拓扑排序就是将入度为0的节点编号入队（因题目要求输出编号小的队伍在前面，所以采用最小堆优先队列来维护条件），当队首元素出队时，依次以它为尾的弧的另一端节点入度减1，同样只要有节点的入度减完为0的就其入队，循环直至不存在无前驱的顶点。

当然此题不存在有向环，因为自己不会和自己比赛，虽然输入有可能出现重复数据即相同的有向边，但是出队的元素已经将其容器中的每个元素编号（即邻接点）的入度都减1，最后有多组相同重复的数据（即邻接点）的入度会减为0，这时入队就不存在有和之前相同的编号，所以不必担心因重边（有向边）而出现输出有相同的顶点编号。

AC代码一：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn=;

 vector<int> vec[maxn];//邻接表，每个节点保存与它相连的边的另一个端点

 priority_queue<int, vector<int>,greater<int> >que;//最小堆优先队列

 int n,m,u,v,num,InDeg[maxn];//记录每个节点的入度，num用来表示节点的个数

 void topsort(){

     num=;

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

         if(!InDeg[i])que.push(i);//预处理，先将入度为0的节点编号入队

     while(!que.empty()){

         int now=que.top();que.pop();num++;

         cout<<now<<(num==n?"\n":" ");//同时输出

         for(unsigned int i=;i<vec[now].size();++i)//遍历每个节点的相关连节点,一次循环可以将与now有边的多个重复点（还是该点）的入度减为0，这时就直接将其入队

             if(--InDeg[vec[now][i]]==)que.push(vec[now][i]);

     }

 }

 int main()

 {

     while(cin>>n>>m){

         for(int i=;i<=n;++i)vec[i].clear();//全部清空

         memset(InDeg,,sizeof(InDeg));//全部顶点的度清0

         while(m--){

             cin>>u>>v;

             vec[u].push_back(v);//u指向v

             InDeg[v]++;//v的入度加1

         }

         topsort();//拓扑排序

     }

     return ;

 }

AC代码二：

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long LL;

 const int maxn = ;

 int cnt, n, m, x, y, num, now, Indeg[maxn], head[maxn];

 struct EDGE{int to, val, next;}edge[ * maxn];

 priority_queue<int, vector<int>, greater<int> > que; ///最小堆

 void add_edge(int u, int v, int w) { ///链式向前星

     edge[cnt].to = v;

     edge[cnt].val = w;

     edge[cnt].next = head[u];

     head[u] = cnt++;

 }

 void topsort() {

     while(!que.empty()) que.pop();

     num = ;

     for(int i = ; i <= n; ++i) ///入度为0的先入队列

         if(!Indeg[i]) que.push(i);

     while(!que.empty()) {

         now = que.top(), que.pop(); num++;

         cout << now << " \n"[num == n];

         for(int i = head[now]; ~ i; i = edge[i].next)

             if(--Indeg[edge[i].to] == ) que.push(edge[i].to);

     }

 }

 int main() {

     while(cin >> n >> m) {

         cnt = ;

         memset(head, -, sizeof(head));

         memset(Indeg, , sizeof(Indeg));

         while(m--) {

             cin >> x >> y;

             add_edge(x, y, ); /// p1 ---> p2 ， p1先拓扑，即排名在前

             Indeg[y]++;

         }

         topsort();

     }

     return ;

 }

巴特西