Cod sursa(job #3264729)

Utilizator Andrei_DumyDumitrescu Andrei-George Andrei_Dumy Data 23 decembrie 2024 16:46:27
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.99 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <list>

using namespace std;


ifstream cin("sortaret.in");
ofstream cout("sortaret.out");


vector<int> adj[50000];
bitset<50000> visited;

list<int> topsort;

int getGraph(const int& m)
{
    int master, slave, first;
    bool flag=true;

    for(int i=0; i<m; i++)
    {
        cin>>master>>slave;

        if(flag)
            first=master, flag=false;

        adj[master].push_back(slave);
    }
    return first;
}

void DFStopsort(int node)
{
    if(!adj[node].empty())
    {
        for(int e: adj[node])
        {
            if(visited[e]==0)
            {
                visited[e]=1;

                DFStopsort(e);
            }
        }
    }
    topsort.push_front(node);
}

void writeList()
{
    for(int node: topsort)
    {
        cout<<node<<" ";
    }
}


int main()
{
    int n, m;

    cin>>n>>m;

    int firstNode = getGraph(m);
    visited[firstNode]=1;

    DFStopsort(firstNode);

    writeList();

    return 0;
}