Cod sursa(job #1366477)

Utilizator PTAdrian64Pop-Tifrea Adrian PTAdrian64 Data 1 martie 2015 08:54:20
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.92 kb
#include <cstdio>
#include <vector>
#define nmax 50010
using namespace std;

vector < int > graph[nmax];
int n,v[nmax],res[nmax];

void read();
void topsort();
void print();

int main(){
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);
    read();
    topsort();
    print();
    return 0;
}
void read(){
    int m;
    scanf("%d %d ",&n,&m);
    int x,y;
    while(m--){
        scanf("%d %d ",&x,&y);
        graph[x].push_back(y);
        v[y]++;
    }
}
void topsort(){
    vector <int> :: iterator it2;
    for(int i = 1;i <= n;i++)if(!v[i])res[++res[0]] = i;
    int x;
    for(int i = 1;i <= n;i++){
        x = res[i];
        for(it2 = graph[x].begin();it2 != graph[x].end();++it2){
            v[*it2]--;
            if(!v[*it2])res[++res[0]] = *it2;
        }
    }
}
void print(){
    for(int i = 1;i <= n;i++)printf("%d ",res[i]);
    printf("\n");
}