Cod sursa(job #1640707)

Utilizator meeprrMelinte Paul meeprr Data 8 martie 2016 18:58:15
Problema Sortare topologica Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream f("sortaret.in");
ofstream g("sortaret.out");

vector <int> graf[50001];
int d[50001],k,st[50001];

void dfs(int x)
{
    int it;
    if(!d[x])
    {
        d[x]=1;
        for(it=0;it<graf[x].size();it++)
        {
            dfs(graf[x][it]);
        }
        k++;
        st[k]=x;
    }
}

int main()
{
    int n,m,x,y;
    f>>n>>m;

    for(int i=1;i<=m;i++)
    {
        f>>x>>y;
        //cerr << x << " " << y << endl;
        graf[x].push_back(y);
    }

    for (int i = 1; i <= n; i++) {
        cerr << "Nodul " << i << ": ";
        for (int j = 0; j < graf[i].size(); j++) {
            cerr << graf[i][j] << ", ";
        }
        cerr << "\n";
    }

    for(int i=1;i<=n;i++) dfs(i);

    for(int i=k;i>=1;i--) g<<st[i]<<" ";
    cerr << "iese";

    return 0;
}