首次架設靜態網站，如有疏失，還請多多包涵。歡迎來信zhuastor@gmail.com

解題心得

複習Topological。

解題想法

就拓樸排序，順便複習了一下DAG無環的條件。

AC code

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
map<int,vector<int>>mp;
int ne[1005]={0};
bool ta[1005];//1
bool check;//2
int pass=0;//3
//1 2 3 都是我設定來判斷環
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin >> n >> m;
    for(int x=0;x<m;x++){
        cin >> a >> b;
        ne[b]++;
        mp[a].push_back(b);
    }
    vector<int>v;
    queue<int>q;
    for(int x=1;x<=n;x++){
        if(ne[x]==0){
            q.push(x);
            break;
        }
    }
    while(!q.empty()){
        if(check)break;
        int now=q.front();
        q.pop();
        if(ta[now]){
            check=true;
            break;
        }
        pass++;
        ta[now]=true;
        v.push_back(now);
        for(int x=0;x<mp[now].size();x++){
            ne[mp[now][x]]--;
            if(ne[mp[now][x]]==0){
                q.push(mp[now][x]);
            }
            if(ne[mp[now][x]]<0){
                check=true;
                break;
            }
        }
    }
    if(pass!=n)check=true;
    if(check){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
        for(int x=0;x<v.size();x++){
            cout << v[x] << endl;
        }
    }
    
    return 0;
}

題目連結 : TOI練習賽2020年4月潛力組