Cod sursa(job #1710947)

Utilizator teodorauTeodora Untaru teodorau Data 30 mai 2016 06:57:04
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.81 kb
#include<fstream>
#include<vector>
using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");
vector <bool> visited;
vector <int> graph [50001];
int afis[50001],n,m,lung;


void DFS(int vertex)
{
    int i;
    if (visited[vertex])
        return;
    visited[vertex]=true;
    for(i=0;i<graph[vertex].size();i++)
        if(!visited[graph[vertex][i]])
            DFS(graph[vertex][i]);

    afis[lung]=vertex;
    lung--;
}


int main()
{

    f>>n>>m;
    visited.resize(n,false);
    int x,y;
    for(int i=0;i<m;i++)
    {
        f>>x>>y;
        graph[x].push_back(y);
    }
    lung=n;
    for(int i=1;i<=n;i++)
    {
        if(!visited[i]);
            DFS(i);
    }

    for(int i=1;i<=n;i++)
    {
        g<<afis[i]<<" ";
    }

    return 0;
}