Cod sursa(job #2166045)

Utilizator mrhammerCiocan Cosmin mrhammer Data 13 martie 2018 15:15:29
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.86 kb
#include<iostream>
#include<fstream>
#include<vector>
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");
int n,m;
vector< vector<int> > mat;
vector<bool> viz;
vector<int> stk;
void dfs(int node)
{
    viz[node] = true;
    for(int i=0;i<mat[node].size();i++)
    {
        if(viz[mat[node][i]] == false)
        {
            dfs(mat[node][i]);
        }
    }
    stk.push_back(node);
}
void topo_sort()
{
    for(int i=0;i<n;i++)
    {
        if(viz[i] == false) dfs(i);
    }
    while(stk.size() > 0)
    {
        fout<<stk[stk.size()-1]+1<<" ";
        stk.pop_back();
    }
}
int main()
{
    fin>>n>>m;
    vector<int> v;
    mat.assign(n,v);
    viz.assign(n,false);
    int k1,k2;
    for(int i=0;i<m;i++)
    {
        fin>>k1>>k2;
        mat[k1-1].push_back(k2-1);
    }
    topo_sort();
}