Cod sursa(job #897488)

Utilizator mucalmicmarcel almic mucalmic Data 27 februarie 2013 20:57:11
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.96 kb
#include <string.h>
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <stdio.h>
 
using namespace std;
 
vector <int> viz, rez,ine;
vector <vector <int> > ed;
 
void parc (int x) {
    int i, j;
     
    viz[x]++;
    rez.push_back(x);
    for (i=0; i<ed[x].size(); i++) {
        ine[ed[x][i]]--;
        if (ine[ed[x][i]] == 0)
            parc(ed[x][i]);
        
    }
 
}
 
 
int main() {
 
freopen("sortaret.in", "r", stdin);
freopen("sortaret.out", "w", stdout);
 
int tst, n, i, j, k, m, n1, n2, l, sum, vmin, arest, maxv;
 
 
cin>>n>>m;
 
viz.resize(n+1, 0);
ed.resize(n+1);
ine.resize(n+1, 0);
 
for (i=0; i<m; i++) {
    cin>>n1>>n2;
    //cout<<n1<<" "<<n2<<endl;
    ed[n1].push_back(n2);
    ine[n2]++;
}
 
for (i=1; i<=n; i++) {
    if (ine[i] == 0 && viz[i] == 0) {
        parc(i);
        //cout<<i<<endl;
        //break;
    }
         
}
 

 
for (i=0; i<rez.size(); i++)
    cout<<rez[i]<<" ";
     
cout<<endl;
 
return 0;
 
}