Cod sursa(job #1194152)

Utilizator BlueStrutAndrei Prahoveanu BlueStrut Data 2 iunie 2014 22:53:42
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> a[100005];
int i, tata[100005], p[100005], x, y, n, m, l;
bool viz[100005];
bool cmp(int a, int b) {return tata[a]>tata[b];}
void dfs(int x){
    vector<int>::iterator it;
    viz[x]=true;
    ++l;
    for (it=a[x].begin();it!=a[x].end();it++) if (!viz[*it]) dfs(*it);
    tata[x]=++l;
    p[x]=x;
}
int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    scanf("%d%d", &n, &m);
    for (i=1;i<=m;i++) {scanf("%d%d", &x, &y); a[x].push_back(y);}
    for (i=1;i<=n;i++) if (!viz[i]) dfs(i);
    sort(p+1, p+n+1, cmp);
    for (i=1;i<=n;i++) printf("%d ", p[i]);
    printf("\n"); return 0;
}