CF645D Robot Rapping Results Report 题解

题目链接：CF645D Robot Rapping Results Report

题意：

\(n\) 个机器人，每个机器人有一个不同的级别，级别介于 \(1\sim n\)，高级别的可以打败低级别的，现在给出 \(n\) 个机器人的 \(m\) 场比赛胜负情况，问最少需要前几场比赛就可以确定每个机器人的级别。

输入格式

第一行两个整数 \(n\) 和 \(m\) 表示机器人个数和比赛场数，之后 \(m\) 行每行两个整数 \(u\) 和 \(v\) 表示机器人 \(u\) 打败机器人 \(v\)。

输出格式

如果这 \(m\) 场比赛可以确定每个机器人的级别则输出最少需要前几场比赛就可以确定，否则输出 \(-1\)。

数据范围

\(2\leq n\leq 10^5\)，\(1\leq m\leq \min(\frac{n\times (n-1)}{2},10^5)\)。

不难发现这里有个单调性

即越多的边越有可能确定每个机器人的级别

当然如果所有边都不能确定的话，就输出无解即可

所以解法一：二分可能的边数，然后topo，时间复杂度 \(O(m \log m)\)

假如在某一时间队列中的元素多于一个，则这个图的拓扑序不只一种即为错误

代码没写，基本上就是topo板子加一个if(q.size()>1) return 0;

解法二：考虑直接topo，然后记录每个结点最少需要几条边才能确定

答案就是所需边数量最大值。

如果某一等级，即代码中的dfn，出现了不止一次

则这两个机器人我们无法确定到底谁更强，则无解

这个解法太难想到了，我看了题解才知道的 qwq

时间复杂度 \(O(n)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1e5+15)

int n,m,ck,pos=1,id[N],in[N],mk[N],dfn[N],head[N];
queue<int> q;
struct Edge{int u,v,id,next;}e[N];
void addEdge(int u,int v,int id)
{
    e[++pos]={u,v,id,head[u]};
    head[u]=pos;
}
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,i); ++in[v];
    }
    for(int i=1; i<=n; i++)
        if(!in[i])
        {
            if(ck) return cout << "-1",0;
            q.push(i); ck=1;
        }
    while(!q.empty())
    {
        int u=q.front(); q.pop();
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            if(dfn[v]==dfn[u]+1) id[v]=min(id[v],e[i].id);
            if(dfn[v]<dfn[u]+1) dfn[v]=dfn[u]+1,id[v]=e[i].id;
            if(!(--in[v])) q.push(v);
        }
    }
    for(int i=1; i<=n; i++)
    {
        if(mk[dfn[i]]) return cout << "-1",0;
        mk[dfn[i]]=1;
    }
    int res=0;
    for(int i=1; i<=n; i++) 
        res=max(res,id[i]);
    cout << res << '\n';
    return 0;
}

参考文献

[1] https://www.luogu.com.cn/blog/EnochWenzhou/solution-cf645d