Cod sursa(job #1750344)

Utilizator matzul98Socaciu Mihai matzul98 Data 29 august 2016 22:31:38
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
/*
9 8
1 2
1 3
3 4
3 5
5 9
4 6
4 7
4 8

6 6
1 2
3 1
3 5
4 1
5 4
6 3
*/
vector<int> V[50001];
int n;
void Citire()
{
   //Graful orientat - retinem cine intra in fiecare nod (grad exterior)
   int m;
   f>>n>>m;

   for(int i=0;i<m; i++)
   {
      int x,y;
      f>>x>>y;
      V[y].push_back(x);
   }
}

bool viz[50001] = {0};
void DFS(int nod)
{
   //Mergem pe nodurile ext a lui nod, iar apoi pe acelea
   for(int i = 0; i < V[nod].size(); i++)
   {
      int temp = V[nod][i];//Prea mult de scris :)
      if(!viz[temp])//Nu a fost vizitat
      {
         DFS(temp);
      }
   }

   if(!viz[nod])
   {
      viz[nod] = true;
      g<<nod<<" ";
   }
}

int main()
{
   Citire();
   for(int i=1; i<=n; i++)
   {
      DFS(i);
   }
}