Cod sursa(job #2664679)

Utilizator miramaria27Stroie Mira miramaria27 Data 29 octombrie 2020 09:28:47
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <list>
#include <fstream>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
list <int> sortaret;
void dfs(int start, list<int> ad[],int visited[], int f[], int &d)
{

    d ++;
    visited[start] = 1;
    for(auto &child : ad[start])
    {
        if(visited[child] == 0)
            dfs(child,ad,visited,f,d);

    }
    f[start] = ++ d;
    sortaret.push_front(start);
}
int main()
{
    int n,m,start;
    fin>>n>>m;
    list <int> ad[n+1];

    for(int i = 0; i < m; i ++)
    {

        int x,y;
        fin >> x >> y;
        ad[x].push_back(y);

    }
    int visited[n+1]= {0};
    int f[n+1] = {0};
    int d = 0;

    for(int i=1; i<=n; i++)
            if(visited[i] == 0)
            {
                start = i;
                dfs(start,ad,visited,f,d);
            }
    for(auto it = sortaret.begin();it!=sortaret.end();it++)
        fout << *it <<" ";
    return 0;
}