现在的位置: 首页 > 综合 > 正文

[HDU 1285]确定比赛顺序[拓扑排序模板题]

2017年12月13日 ⁄ 综合 ⁄ 共 560字 ⁄ 字号 评论关闭

题意就是拓扑排序啦~

坑:

有重边 > <

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 505;
int a[MAXN][MAXN];
int in[MAXN],ans[MAXN];
int n,m;

bool TopologicalSort()
{
    for(int i=1;i<=n;i++)
    {
        int j = 1;
        while(in[j]!=0)
        {
            j++;
            if(j>n)
                return false;
        }
        ans[i] = j;
        in[j] = -1;
        for(int k = 1;k<=n;k++)
        {
            if(a[j][k]>0) in[k] -= a[j][k];
        }
    }
    for(int i=1;i<=n;i++)
    {
        printf("%d%c",ans[i],(i==n)?'\n':' ');
    }
    return true;
}
inline void clear()
{
    memset(a,0,sizeof(a));
    memset(in,0,sizeof(in));
}
int main()
{
    while(scanf("%d %d",&n,&m)==2)
    {
        int x,y;
        clear();
        for(int i=0;i<m;i++)
        {
            scanf("%d %d",&x,&y);
            a[x][y]++;
            in[y]++;
        }
        TopologicalSort();
    }
}

抱歉!评论已关闭.