SMMR-T153: Food Web

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef struct chain{
    int s;
    int dis;
    bool operator < (const chain &rhs)const{
        return dis > rhs.dis;
    }
}chain;

enum color{
    white, grey, black
};

vector<vector<int>> adj;
vector<bool> start;
int nv, ne;
bool cycle;

void PrintAdj(){
    for(int i = 1; i <= nv; ++i){
        cout << i << " | ";
        for(auto v : adj[i]){
            cout << v << " ";
        }
        cout << "\n";
    }
    return;
}

vector<color> colors;
bool DFSCycle(int u){
    if(colors[u] == grey){
        return true;
    }
    if(colors[u] == black){
        return false;
    }
    colors[u] = grey;
    for(auto v : adj[u]){
        if(DFSCycle(v)){
            return true;
        }
    }
    colors[u] = black;
    return false;
}

vector<chain> dist;
void FindPredator(int start){
    queue<int> q;
    dist[start] = {start, 0};
    q.push(start);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(auto v : adj[u]){
            if(dist[u].dis + 1 > dist[v].dis){
                dist[v] = {v, dist[u].dis + 1};
                q.push(v);
            }
        }
    }
    return;
}

int main(){

    int u, v;

    scanf("%d %d", &nv, &ne);
    adj.assign(nv + 1, vector<int>());
    start.assign(nv + 1, true);
    for(int i = 0; i < ne; ++i){
        scanf("%d %d", &u, &v);
        adj[u].push_back(v);
        start[v] = false;
    }

    /// Check Cycle
    colors.assign(nv + 1, white);
    cycle = false;
    for(int i = 1; i <= nv; ++i){
        if(colors[i] == white){
            if(DFSCycle(i)){
                cycle = true;
                break;
            }
        }
    }

    /// Print
    if(cycle){
        cout << "No";
    } else {
        dist.assign(nv + 1, {0, 0});
        for(int i = 1; i <= nv; ++i){
            if(start[i]){
                FindPredator(i);
            }
        }
        cout << "Yes\n";
        sort(dist.begin(), dist.end());
        for(int i = 0; i <= nv; ++i){
            if(dist[i].s != 0){
                cout << dist[i].s << " ";
            }
        }
    }


    return 0;
}