CCCPaste

Untitled

#include 
#include 
#include 
#include 
#include 
using namespace std;
int n, m;
vector graph[300005];
int color[300005];
bool visited[300005];
stack st;
bool cycle(int node) {
    color[node] = 1;
    for(int i = 0; i < (int) graph[node].size(); i++) {
        int neigh = graph[node][i];
        if(color[neigh] == 0) {
            if(cycle(neigh)) {
                return true;
            }
        }
        else if(color[neigh] == 1) {
            return true;
        }
    }
    color[node] = 2;
    return false;
}
void dfs(int node) {
    visited[node] = true;
    for(int i = 0; i < (int) graph[node].size(); i++) {
        int neigh = graph[node][i];
        if(!visited[neigh]) {
            dfs(neigh);
        }
    }
    st.push(node);
}
int main()
{
    cin >> n >> m;
    memset(color, 0, sizeof color);
    for(int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        graph[a].push_back(b);
    }
    for(int i = 0; i < n; i++) {
        if(color[i] == 0) {
            if(cycle(i)) {
                cout << "IMPOSSIBLE\n";
                return 0;
            }
        }
    }
    for(int i = 0; i < n; i++) {
        if(!visited[i]) {
            dfs(i);
        }
    }
    while(!st.empty()) {
        cout << st.top() + 1 << " ";
        st.pop();
    }
    return 0;
}


/*
 ########
 #M..A..#
 #.#.M#.#
 #M#..#..
 #.######
 
 **/