【拓扑排序】HDU 1285 确定比赛名次

http://acm.hdu.edu.cn/showproblem.php?pid=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

#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;

int ind[505], n;    //ind: 入度

struct node{
    int son;    //儿子的编号
    node *next;    //指向下一个儿子，即为son的兄弟
}*N[505];

void init ()    //初始化
{
    for (int i = 1; i <= n; i++)
        ind[i] = 0, N[i] = NULL;
}

void insert (int a, int b)    //b插入作为a的儿子，a这个链表表示a的所有儿子，不包括孙子
{
    node *p = new node;
    p->son = b;
    p->next = N[a];
    N[a] = p;
}

int main()
{
    int m, a, b, i, j;
    while (~scanf ("%d%d", &n, &m))
    {
        init();
        while (m--)
        {
            scanf ("%d%d", &a, &b);
            insert (a, b);
            ind[b]++;
        }
        for (i = 0; i < n; i++)    //寻找n次入度为0的点即可
        {
            for (j = 1; j <= n; j++)
            {
                if (ind[j] == 0)    //找到一个
                {
                    ind[j] = -1;    //删点
                    if (i < n - 1)
                        printf ("%d ", j);
                    else printf ("%d\n", j);
                    for (node *p = N[j]; p; p = p->next)
                        ind[p->son]--;    //j的儿子入度-1
                    break;    //找另外一个
                }
            }
        }
    }
    return 0;
}

评论

2 楼 基德KID.1412 2011-08-10  

sgeteternal 写道

爽晒啦~

爽到恒

1 楼 sgeteternal 2011-08-10  

爽晒啦~