Cod sursa(job #678014)

Utilizator pikuAnca Miihai piku Data 10 februarie 2012 21:41:50
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<cstdio>
#include<cstdlib>
#include<list>
#include<vector>

using namespace std;

int n, m;
vector<int> graph[50001];

list<int> path;
int seen[50001];

void dfs(int node)
{
  seen[node] = 1;
  int i;
  for(i = 0; i < graph[i].size(); ++i)
    if(seen[graph[node][i]] != 1)
      dfs(graph[node][i]);
  path.push_back(node);
}

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

  scanf("%d %d", &n, &m);

  int i;
  for (i = 1; i <= m; i++)
  {
    int a, b;
    scanf("%d %d", &a, &b);
    graph[a].push_back(b);
  }

  for (i = 1; i <= n; i++)
    if (seen[i] != 1)
      dfs(i);

  for(list<int>::iterator it = path.begin(); it != path.end(); it++)
    printf("%d ", *it);

  return 0;
}