Cod sursa(job #1094207)

Utilizator ccristianCristian Chirion ccristian Data 28 ianuarie 2014 23:51:37
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1 kb
#include <fstream>
#include <vector>
using namespace std;
int  k=0;
int timp[50001], vis[50001];
void dfs(int nod, vector <int> a[], int n){
    vis[nod]=1;
    int i;
    k++;
    for (i=0; i<a[nod].size(); i++){
        if (vis[a[nod][i]]==0){dfs(a[nod][i], a, n);}
    }
    k++;
    timp[nod]=k;

}

int main()
{
    ifstream in("sortaret.in");
    ofstream out("sortaret.out");
    int n, m, e1, e2, i, j, aux;
    in>>n>>m;
    vector <int> a[n+1];
    for (i=1; i<=m; i++){
        in>>e1>>e2;
        a[e1].push_back(e2);
    }
    for (i=1; i<=n; i++){
        vis[i]=0;
    }


    for (i=1; i<=n; i++){
        if(vis[i]==0){dfs(i, a, n);}
    }

    int ordine[n+1];
    for (i=1; i<=n; i++){
        ordine[i]=i;
    }
    for (i=1; i<=n; i++){
        for (j=i; j<=n; j++){
            if (timp[j]<timp[j+1]){aux=ordine[j]; ordine[j]=ordine[j+1]; ordine[j+1]=aux;}
        }
    }
    for (i=1; i<=n; i++){
        out<<ordine[i]<<" ";
    }

    return 0;
}