G8010 [GESP202412 八级] 排队 题解

知识点：拓扑排序、图的度数、排列计数。

解题思路

对相邻前后关系去重，每人入度、出度都不得超过1且不能有环。合法关系把人压成若干有固定内部顺序的链，链数为n-去重边数，答案是链数阶乘。

为什么正确

度数限制保证分量只可能是链或环，拓扑排序排除环；各链内部不可拆，任意排列链就一一对应所有合法队伍。

易错点

约束要求相邻而非仅先后；重复关系不能重复扣减链数，自环直接无解。

复杂度

时间O(m log m+n)，空间O(n+m)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<int>in(n+1),out(n+1);
    set<pair<int,int>>e;
    bool ok=true;
    while(m--) {
        int u,v;
        cin>>u>>v;
        e.insert({u,v});
    }
    for(auto [u,v]:e) {
        if(u==v||++out[u]>1||++in[v]>1)ok=false;
    }
    vector<vector<int>>g(n+1);
    for(auto [u,v]:e)g[u].push_back(v);
    queue<int>q;
    for(int i=1;i<=n;i++)if(!in[i])q.push(i);
    int seen=0;
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        seen++;
        for(int v:g[u])if(--in[v]==0)q.push(v);
    }
    if(!ok||seen<n) {
        cout<<0;
        return 0;
    }
    long long ans=1;
    for(int i=1;i<=n-(int)e.size();i++)ans=ans*i%1000000007;
    cout<<ans;
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用14个自行生成的测试点。