Cod sursa(job #1941520)

Utilizator MaligMamaliga cu smantana Malig Data 27 martie 2017 13:03:02
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;
ifstream in("sortaret.in");
ofstream out("sortaret.out");

const int NMax = 5e4 + 5;
typedef long long ll;

int N,M,nrSol;
int sol[NMax];
bool check[NMax];
vector<int> v[NMax];

void dfs(int);

int main()
{
    in>>N>>M;
    for (int i=1;i<=M;++i) {
        int x,y;
        in>>x>>y;
        v[x].push_back(y);
    }

    for (int i=1;i<=N;++i) {
        if (check[i]) {
            continue;
        }

        dfs(i);
    }

    for (int i=N;i>0;--i) {
        out<<sol[i]<<' ';
    }

    in.close();out.close();
    return 0;
}

void dfs(int x) {
    check[x] = true;

    for (int k=0;k < (int)v[x].size();++k) {
        int son = v[x][k];
        if (check[son]) {
            continue;
        }

        dfs(son);
    }

    sol[++nrSol] = x;
}