Mai intai trebuie sa te autentifici.
Cod sursa(job #1071825)
| Utilizator | 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;
}
