Cod sursa(job #2676916)

Utilizator MateGMGozner Mate MateGM Data 25 noiembrie 2020 12:50:32
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;

void dfs(const vector<vector<int> > &adj,int m,vector<bool>&ell,int start,vector<int>&l)
{
    ell[start]=true;
    for(auto sz:adj[start])
    {
        if(!ell[sz])
            dfs(adj,m,ell,sz,l);
    }
    l.push_back(start);

}
int main()
{
    ifstream be("sortaret.in");
    ofstream ki("sortaret.out");
    int n,m;
    be>>n>>m;
    vector<vector<int> > adj(n+1);
    for(int i=1;i<=m;i++)
    {
        int u,v;
        be>>u;
        be>>v;
        adj[u].push_back(v);
    }
    vector<bool>ell(n+1,false);
    vector<int>l;
    for(int i=1;i<=n;i++)
    {
        if(!ell[i])
        {
            dfs(adj,m,ell,i,l);
        }
    }
    reverse(l.begin(),l.end());
    for(vector<int>::iterator it=l.begin();it!=l.end();it++)
        ki<<*it<<" ";

    return 0;

}