Cod sursa(job #3264731)

Utilizator Andrei_DumyDumitrescu Andrei-George Andrei_Dumy Data 23 decembrie 2024 17:05:25
Problema Sortare topologica Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <unordered_set>
#include <bitset>
#include <list>

using namespace std;


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


unordered_set<int> adj[50001];
bitset<50001> visited, slaves;
int masters[50001];

list<int> topsort;


int getGraph(const int& m)
{
    int master, slave, first, j=0;

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

        if(slaves[master]==0)
        {
            masters[j++]=master;
            //cout<<masters[i-1]<<" "<<i-1;
            slaves[master]=1;
        }

        slaves[slave]=1;

        adj[master].insert(slave);
    }
    return j;
}

void DFStopsort(int node)
{
    if(visited[node]==1)
        return;

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

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


int main()
{
    int n, m;

    cin>>n>>m;

    int mastersc = getGraph(m);    

    for(int i=0; i<mastersc; i++)
        DFStopsort(masters[i]);

    writeList();

    return 0;
}