Cod sursa(job #2335914)

Utilizator RK_05Ivancu Andreea Raluca RK_05 Data 4 februarie 2019 17:10:24
Problema Sortare topologica Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
/*
    Pe graf orientat, desi se poate si pe graf neorientat, trebuie numai un pic modificat
*/
#include <fstream>
#include <iostream>
#include <vector>
#define nmax 250

using namespace std;

vector<int> G[nmax];
int n, m, x, y, viz[nmax], ord[nmax], k;

ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

void read(){
    fin >> n >> m;
    for(int i = 0; i < m; ++i){
        fin >> x >> y;
        G[x].push_back(y);
    }
}

void DFS(int nod){
    viz[nod] = 1;
    for(int i = 0; i < G[nod].size(); ++i){
        if(viz[G[nod][i]] == 0)
            DFS(G[nod][i]);
    }
    ord[k] = nod;
    k++;
}


void sol(){
    for(int i = 1; i <= n; ++i){
        if(viz[i] == 0)
            DFS(i);
    }
    for(int i = k - 1; i >= 0; --i)
        fout << ord[i] << " ";
}

int main(){

    read();
    sol();
    return 0;
    fin.close();
}