洛谷P1960 郁闷的记者 题解

题目链接：P1960 郁闷的记者

题意：

你是一个体育报社的记者，你接受到一个艰难的任务：有N支足球队参加足球比赛，现在给你一些比赛的结果，需要你给出各支球队的排名，从1到N。

以下是给你的一些信息：

(1)没有平局；

(2)不同的球队排名不能相同；

(3)对于所有满足l≤a<b≤n，第a名的球队一定可以打败第b名的球队。

给你部分比赛结果，要求给出排名，并且判断是否存在另一种排名方法满足给你的比赛结果。

输入格式

第一行输入N(1≤N≤5000)，表示球队的数量，编号为l到N。第二行输入M(1≤M≤100,000)，表示给出的比赛场数。接下来M行，每行两个整数X_i，Y_i，表示X_i能打败Y_i。

输出格式：

输出包含N+1行，前N行描述球队的排名，第i个数表示第i名的球队，第N+1行包含一个整数，如果为0表示不存在其他的排名方法，如果为1表示还有其他的排名方法。

数据范围：

\(1\le N\le 5000,~1\le M\le 10^5\) 。

注意到如果某一时刻出现多个度数为 \(0\) 的结点，则拓扑序不唯一。

时间复杂度 \(\mathcal{O}(n)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(5e3+15))
#define M ((int)(1e5+15))

queue<int> q;
int n,m,pos=1,tmp,c,head[N],in[N];
struct Edge{ int u,v,next; } e[M];
void addEdge(int u,int v)
{ e[++pos] = {u,v,head[u]}; head[u] = pos; ++in[v]; }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,u,v; i<=m; i++) { cin >> u >> v; addEdge(u,v); }
    for(int i=1; i<=n; i++) if(!in[i]) q.push(i), ++tmp;
    if(tmp > 1) c = 1; tmp = 0;
    while(!q.empty())
    {
        int u = q.front(); q.pop();
        cout << u << '\n'; tmp = 0;
        for(int i=head[u]; i; i=e[i].next)
        {
            int v = e[i].v;
            if(!(--in[v])) { ++tmp; q.push(v); }
        }
        if(tmp > 1) c = 1; tmp = 0;
    }
    cout << c << '\n';
    return 0;
}