Cod sursa(job #2194062)

Utilizator pitradaPit-Rada Ionel-Vasile pitrada Data 12 aprilie 2018 04:35:08
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <algorithm>
#include<cstring>
#define Nmax 50002
#define Mmax 100002
using namespace std;
ifstream fin("sortaret.in");
ofstream fout("sortaret.out");

struct legatura{
    int x,y;
};
legatura L[Mmax];
int N,M,D[Nmax],viz[Nmax],X[Nmax],A[2*Mmax],K,Start[Nmax],P[Nmax];
///D[x]=gradul lui x
///vecinii lui x se afla in secventa a[1+Start[x]]...A[D[x]+Start[x]]
///al i-lea vecin al lui x este A[i+Start[x]]
void citire(){
    int i,j,l;
    fin>>N>>M;
    for(l=1;l<=M;l++){
        fin>>i>>j;
        L[l]={i,j};
        D[i]++; D[j]++;
    }
}
void construire_liste_adiacenta(){
    int i,x,y;
    Start[1]=0;P[1]=0;
    for(i=2;i<=N+1;i++){
        Start[i]=Start[i-1]+D[i-1];
        P[i]=Start[i];
    }
    for(i=1;i<=M;i++){
        x=L[i].x; y=L[i].y;
        A[++P[x]]=y;
        A[++P[y]]=x;
    }
}
void DFS(int vf){
    int i,x;
    viz[vf]=1;
    for(i=1;i<=D[vf];i++){
        x=A[Start[vf]+i];
        if(viz[x]==0){
            DFS(x);
        }
    }
    X[++K]=vf;
}

int main(){
    citire();
    K=0;
    for(int i=1;i<=N;i++){
        if(viz[i]==0){
            DFS(i);
        }
    }
    for(int i=N;i>=1;i--){
        fout<<X[i]<<" ";
    }
    fout.close();
    fin.close();
    return 0;
}