Cod sursa(job #730158)

Utilizator a08iAndrei Ionescu a08i Data 5 aprilie 2012 13:49:57
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include<cstdio>
#include<iostream>
#include<vector>
#include<stack>

using namespace std;

typedef vector< vector<int> > Graph;
stack<int> result;

void DFS(Graph &graph, int i, vector<int> &explored)
{
  explored[i] = 1;
  for(int j=0; j< graph[i].size(); j++)
  {
    if(explored[graph[i][j]] == 0)
    {
      DFS(graph, graph[i][j], explored);
    }
  }
  result.push(i);
}

int main()
{

  freopen("sortaret.in", "r", stdin);
  freopen("sortaret.out", "w", stdout);

  int N, M, v1, v2;

  scanf("%d %d", &N, &M);

  Graph graph(N+1, vector<int>());
  vector<int> explored(N+1,0);

  for(int i=0; i<M; i++)
  {

    scanf("%d %d", &v1, &v2);
    graph[v1].push_back(v2);
  }

  // dfs-loop
  for(int i=1; i<graph.size(); i++)
  {
    if(explored[i] == 0)
    {
      DFS(graph, i, explored);
    }
  }

  while(!result.empty())
  {
    cout << result.top() << " ";
    result.pop();
  }

  return 0;
}