1 条题解

  • 1
    @ 2026-10-13 14:42:45

    SOLUTION

    结论:反向连边,找字典序最大的拓扑序即为答案。

    显然直接找字典序最小的假了,如 n=3,3→1n=3,3 \to 1 连边,答案 3 1 2,错解 2 1 3。

    对于结论,我不会证,但是我找不到反例,我就认为他是对的了。

    具体地,建反图,并用 std::priority_queue 代替 std::queue。

    证明

    CODE

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,m;
    map<pair<int,int>,int> mp;
    vector<int> G[101000];
    int ind[101000];
    priority_queue<int> pq;
    vector<int> vec;
    void topo(){
        vec.clear();
        for(int i=1;i<=n;i++){
            if(!ind[i]) pq.push(i);
        }
        while(!pq.empty()){
            int u=pq.top();
            vec.push_back(u),pq.pop();
            for(int v:G[u]){
                if(!(--ind[v])) pq.push(v);
            }
        }
        if(vec.size()<n) cout<<"No Solution!";
        else{
            reverse(vec.begin(),vec.end());
            for(int i:vec) cout<<i<<' ';
        }
        cout<<'\n';
    }
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>T;
        while(T--){
            cin>>n>>m;
            for(int i=1;i<=n;i++){
                G[i].clear();
                ind[i]=0;
            }
            mp.clear();
            for(int i=1;i<=m;i++){
                int u,v;
                cin>>u>>v;
                if(mp[{u,v}]) continue;
                mp[{u,v}]=1;
                G[v].push_back(u);
                ind[u]++;
            }
            topo();
        }
        return 0;
    }
    
    • 1

    信息

    ID
    439
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    65
    已通过
    16
    上传者