Cod sursa(job #2664001)

Utilizator paulaiugaPaula Iuga paulaiuga Data 27 octombrie 2020 19:02:57
Problema Sortare topologica Scor 50
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

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

//daca exista un arc ( i, j ), atunci i apare inaintea lui j in sortare
vector<int> adiacenta[100009];
vector <int> sortare;
bool vizitat[100009] = {false};

void DFS(int nod)
{
    vizitat[nod] = true;
    for(size_t i=0; i< adiacenta[nod].size(); i++)
    {
        if(!vizitat[adiacenta[nod][i]])
        {
            vizitat[i] = true;
            DFS(adiacenta[nod][i]);
        }

    }
     sortare.push_back(nod);
}

int main()
{
int N,M,x,y;
    in>>N>>M;
     for(int i =1; i <=M ;i++)
    {
        in>>x>>y;
        adiacenta[x].push_back(y);
        //graf orientat x y  muchie => fdoar x e vecinul lui y

    }

    sortare.clear();

    for(int i = 1; i <= N; i++)
    {
        if(!vizitat[i])
        {
             DFS(i);

        }
    }

    reverse(sortare.begin(), sortare.end());
    for(size_t i=0; i< sortare.size(); i++)
        out<<sortare[i]<<" ";
   out<<"\n";

    return 0;
}