C++ 基礎題 陣線推進(資芽OJ)

直接附上程式碼。

#include<bits/stdc++.h>
using namespace std;

set<int> g[100010];
int ind[100010];
int n,m;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int t;
    cin>>t;
    while(t--){
        ans="";ct=0;
        for(int i=0;i<100010;i++){
            g[i].clear();
            ind[i]=0;
            v[i]=0;
        }

        cin>>n>>m;
        for(int i=0;i<m;i++){
            int to,from;
            cin>>from>>to;
            g[from].insert(to);
        }

        for(int i=0;i<n;i++) 
            for(auto a:g[i])
                ind[a]++;
        vector<int> ans;
        priority_queue<int,vector<int>,greater<int>> topo;
        for(int i=0;i<n;i++){
            if(ind[i]==0){
                topo.push(i);
            }
        }

        while(!topo.empty()){
            int now=topo.top();
            topo.pop();
            ans.push_back(now);
            for(auto next:g[now]){
                if(--ind[next] ==0){
                    topo.push(next);
                }
            }
        }

        if(ans.size()==n){
            cout<<ans[0];
            for(int i=1;i<ans.size();i++) cout<<" "<<ans[i];
            cout<<"\n";
        }else{
            cout<<"QAQ\n";
        }
    }
    return 0;
}

雖然標題標基礎題,然而卻耗費了我許多時間,所幸最後還是答出來了。

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *