Cod sursa(job #1636366)

Utilizator GabiADAndrei Gabriel GabiAD Data 7 martie 2016 09:18:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>

using namespace std;

vector <vector <int>> graph;
vector <int> visited;
unsigned int n, m;

stack<int> sol; 


void DFS(unsigned int vertex)
{
  
  if(vertex < 0 || vertex > n-1)
    return;

  stack <int> s;
  int element;
  bool found;
  unsigned int i;

  s.push(vertex);

  visited[vertex] = true;
  //cout << vertex + 1 << endl;
  while(!s.empty())
    {
      element = s.top();
      found = false;
      
      for (i = 0; i < graph[element].size() && !found; i++)
	{
	  if(!visited[graph[element][i]])
	    {
	      found = true;
	      //cout << graph[element][i] + 1 << endl;
	    }

	}
	  
	  if(found)
	    {
	      i--;
	      s.push(graph[element][i]);

	      visited[graph[element][i]] = true;

	    }
	  else
	    {
	      sol.push(element);
	      s.pop();


	    }
	
    }


}


int main()
{
  ifstream sorti("sortaret.in");
  ofstream sorto("sortaret.out");
  
  sorti >> n >> m;
  graph.resize(n);

  visited.resize(n, false);

  int x, y;
  unsigned int i;

  for (i = 0; i < m; i++)
    {
      sorti >> x >> y;

      x--;
      y--;

      graph[x].push_back(y);
    }

  for (i = 0; i < visited.size() && i < n; i++)
    if(!visited[i])
	DFS(i);
  
  for (i = 0; i < n; i++)
    {
      sorto << sol.top() + 1 << " ";
      sol.pop();
    }

  
  return 0;
}