HDOJ1285 比赛排名（拓扑排序）

拓扑排序（适用于有向无环图）：

1）选一个入度为0的点p输出；

2）从图中删除p点

3）将p全部后继点的入度-1

4）重复1-3，直到全部点都输出

题目：

1285

确定比赛名次

/*
需要一个存入度的数组indegree[]
用邻接矩阵存储图
Map[i][j] = 1表示有从i到j的边，及i是j的前驱结点
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define N 505
int Map[N][N],indegree[N];
int n,m,cnt;

void main()
{
    int i,a,b,idx;
    while (scanf("%d%d",&n,&m)!=EOF)//n个队伍、m条数据
    {
        //初始化
        memset(Map,0,sizeof(Map));
        memset(indegree,0,sizeof(indegree));
        //读取图
        for (i=0 ; i<m ; i++)
        {
            cin>>a>>b;
            if (!Map[a-1][b-1])//避免重复边
            {
                Map[a-1][b-1] = 1;
                indegree[b-1]++;
            }
        }
        //拓扑排序
        cnt = 0;
        while (cnt<n)//入栈的元素为n个表示全部排完了。
        {
            //找一个入度为0的点idx
            for (idx=0 ; indegree[idx] != 0 ; idx++);
            //避免再次统计idx点，把入度改为-1
            indegree[idx] = -1;
            //所有idx的后继结点入度-1
            for (i=0;i<n;i++)
            {
                if (Map[idx][i] == 1)    indegree[i]--;
            }
            cout<<idx+1<<" ";
            cnt++;
        }
        cout<<endl;
    }
}