Cod sursa(job #2350060)

Utilizator natrovanCeval Marius natrovan Data 20 februarie 2019 23:49:47
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>

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

list<int>graf[50100];
int marked[50100];
int n,x,y,i,X,m;
queue<int>myQueue;

void DFS(int v, list<int>graf[])
{
    marked[v] = true;
    for(list<int>::iterator it = graf[v].begin(); it != graf[v].end(); it++)
        if(!marked[*it])
            DFS(*it, graf);
    myQueue.push(v);
}

int main()
{
    fin>>n>>m;

    for(i = 1; i<= m; i++)
    {
        fin>>x>>y;
        graf[y].push_back(x);
    }

    for(i = 1; i<= n; i++)
    {
        graf[i].sort();
        graf[i].unique();
    }

    for(i = 1; i<= n; i++)
    {
         if(!marked[i])
            DFS(i, graf);
    }

    while(!myQueue.empty())
    {
        fout<<myQueue.front()<<' ';
        myQueue.pop();
    }

    return 0;
}