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=505;
vector<int> vec[maxn];//邻接表，每个节点保存与它相连的边的另一个端点
priority_queue<int, vector<int>,greater<int> >que;//最小堆优先队列
int n,m,u,v,num,InDeg[maxn];//记录每个节点的入度，num用来表示节点的个数
void topsort(){
    num=0;
    for(int i=1;i<=n;++i)
        if(!InDeg[i])que.push(i);//预处理，先将入度为0的节点编号入队
    while(!que.empty()){
        int now=que.top();que.pop();num++;
        cout<<now<<(num==n?"
":" ");//同时输出
        for(unsigned int i=0;i<vec[now].size();++i)//遍历每个节点的相关连节点,一次循环可以将与now有边的多个重复点（还是该点）的入度减为0，这时就直接将其入队
            if(--InDeg[vec[now][i]]==0)que.push(vec[now][i]);
    }
}
int main()
{
    while(cin>>n>>m){
        for(int i=1;i<=n;++i)vec[i].clear();//全部清空
        memset(InDeg,0,sizeof(InDeg));//全部顶点的度清0
        while(m--){
            cin>>u>>v;
            vec[u].push_back(v);//u指向v
            InDeg[v]++;//v的入度加1
        }
        topsort();//拓扑排序
    }
    return 0;
}

 AC代码二：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 505;
int cnt, n, m, x, y, num, now, Indeg[maxn], head[maxn];
struct EDGE{int to, val, next;}edge[2 * 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 = 0;
    for(int i = 1; i <= n; ++i) ///入度为0的先入队列
        if(!Indeg[i]) que.push(i);
    while(!que.empty()) {
        now = que.top(), que.pop(); num++;
        cout << now << " 
"[num == n];
        for(int i = head[now]; ~ i; i = edge[i].next)
            if(--Indeg[edge[i].to] == 0) que.push(edge[i].to);
    }
}
int main() {
    while(cin >> n >> m) {
        cnt = 0;
        memset(head, -1, sizeof(head));
        memset(Indeg, 0, sizeof(Indeg));
        while(m--) {
            cin >> x >> y;
            add_edge(x, y, 0); /// p1 ---> p2 ， p1先拓扑，即排名在前
            Indeg[y]++;
        }
        topsort();
    }
    return 0;
}