Cod sursa(job #1651305)

Utilizator EberardoVladianu Cosmin Eberardo Data 12 martie 2016 23:23:30
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include <fstream>
#include <vector>
#include <stack>
#include<queue>
using namespace std;

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

int n,m;

vector<vector<int> > lista_adicenta;
vector<bool>viz;
queue<int> q;
stack<int> s,s_afisare;

void citire()
{
    int i,nod1,nod2;
    fin>>n>>m;
    lista_adicenta.resize(n+1);
    viz.resize(n+1);

    for(i=1;i<=m;i++)
    {
        fin>>nod1>>nod2;
        lista_adicenta[nod1].push_back(nod2);
    }

}

void dfs()
{
    int nod_curent;
    bool ok=false;
    vector<int>::iterator it;
    while(!s.empty())
    {
        ok=false;
        nod_curent=s.top();
        for(it=lista_adicenta[nod_curent].begin();it!=lista_adicenta[nod_curent].end();it++)
        {
            if(viz[*it]==false)
            {
                viz[*it]=true;
                s.push(*it);
                ok=true;
                break;
            }
        }
        if(ok==false)
        {
        s_afisare.push(nod_curent);
        s.pop();
        }
    }
}

void afisare()
{
    int nod_curent;
    while(!s_afisare.empty())
    {
        nod_curent=s_afisare.top();
        s_afisare.pop();
        fout<<nod_curent<<' ';
    }
}

void rezolvare()
{
    int i;
    for(i=1;i<=n;i++)
    {
        if(viz[i]==false)
        {
            viz[i]=true;
            s.push(i);
            dfs();
        }
    }
    afisare();
}

int main()
{
    citire();
    rezolvare();
    return 0;
}