Cod sursa(job #2130303)

Utilizator NannyiMaslinca Alecsandru Mihai Nannyi Data 13 februarie 2018 16:39:51
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.83 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define nmax 50005
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector<int>Q[nmax],W;
int n,m;
bool viz[nmax];

void dfs(int nod)
{
    viz[nod]=true;
    for (vector<int>::iterator w=Q[nod].end()-1;w!=Q[nod].begin()-1;--w)
    {
        if (!viz[*w])
            dfs(*w);
    }
    W.push_back(nod);
}

void read()
{
    f>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        int a,b;
        f>>a>>b;
        Q[a].push_back(b);
    }
}

void solve()
{
    for (int i=1; i<=n; ++i)
        if (!viz[i])
            dfs(i);
}

void afis()
{
    for (vector<int>::iterator w=W.end()-1;w!=W.begin()-1;--w)
        g<<*w<<' ';
}

int main()
{
    read();
    solve();
    afis();
    return 0;
}