Cod sursa(job #1071825)

Utilizator dumytruKana Banana dumytru Data 3 ianuarie 2014 15:42:44
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;

unsigned n,m,time;

vector<vector<unsigned> >graf;
vector<unsigned> times, is_visited,sol;
unsigned current_time;

void DFS_Visit(unsigned currentNode)
{
    unsigned i,len=graf[currentNode].size();
    is_visited[currentNode] = 1;
    for(i=0;i<len;i++)
    {
        if(is_visited[graf[currentNode][i]] == 0)
        {
            DFS_Visit(graf[currentNode][i]);
        }
    }
    is_visited[currentNode] = 2;
    current_time++;
    times[currentNode]=current_time;
    sol.push_back(currentNode);
}

void DFS()
{
    current_time=0;

    for(unsigned i=1;i<=n;i++)
    {
        if(is_visited[i]==0)
            DFS_Visit(i);
    }
}

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

    unsigned i,u,v;
    scanf("%d %d",&n,&m);

    graf.resize(n+1);times.resize(n+1);is_visited.resize(n+1);

    for(i=1;i<=m;i++)
    {
        scanf("%d %d",&u,&v);
        graf[u].push_back(v);
    }
    DFS();
    sol.resize(n+1);
    //for(i=1;i<=n;i++)
    //    sol[i]=times[times[i]];
    for(i=1;i<=n;i++)cout<<sol[n-i]<<' ';
    return 0;
}