Cod sursa(job #1382114)

Utilizator mariusadamMarius Adam mariusadam Data 8 martie 2015 14:50:17
Problema Sortare topologica Scor 70
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <fstream>
#include <iostream>
#include <vector>

using namespace std;

ifstream r("sortaret.in");
ofstream w("sortaret.out");

bool viz[50002];
int n,k=0,m;
int top[50002],start[50002];
int g[2][20000];

void df(int nod){
    int p;
    viz[nod]=true;
    p=start[nod];
    while (p){
        if (!viz[g[0][p]])
            df(g[0][p]);
        p=g[1][p];
    }
    k++;
    top[k]=nod;
}

void read(){
    int k,i,j;
    r>>n>>m;
    for(k=1;k<=m;k++){
        r>>i>>j;
        g[0][k]=j;
        g[1][k]=start[i];
        start[i]=k;
    }
}

int main(){
    int i;
    read();
    for (i=1;i<=n;i++)
        if (!viz[i])
            df(i);
    for (i=k;i>=1;i--)
        w<<top[i]<<" ";
    w<<"\n";
    r.close();
    w.close();
    return 0;
}