Cod sursa(job #2526154)

Utilizator stefanpiturStefan Alexandru Pitur stefanpitur Data 18 ianuarie 2020 12:11:52
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.87 kb
#include <iostream>
#include <cstdio>
using namespace std;
const int nmax = 50001;
const int mmax = 100001;
int lst[nmax],vf[mmax],urm[mmax],nr,n;
int sol[nmax],l;
bool visited[nmax];

void adauga(int x, int y){
    vf[++nr] = y;
    urm[nr] = lst[x];
    lst[x] = nr;
}

void dfs(int node){
    visited[node] = true;
    for(int p=lst[node]; p!=0; p=urm[p]){
        int next = vf[p];
        if(!visited[next])
            dfs(next);
    }
    sol[l++] = node;
}

int main()
{
    FILE *fin, *fout;
    int m,i,x,y;
    fin = fopen("sortaret.in","r");
    fout = fopen("sortaret.out","w");
    fscanf(fin,"%d %d",&n,&m);
    for(i=0; i<m; i++){
        fscanf(fin,"%d %d",&x,&y);
        adauga(x,y);
    }
    for(i=1; i<=n; i++)
        if(!visited[i])
            dfs(i);
    for(i=l-1; i>=0; i--)
        fprintf(fout,"%d ",sol[i]);
    fclose(fin);
    fclose(fout);
    return 0;
}