Cod sursa(job #1825703)

Utilizator andreicoman299Coman Andrei andreicoman299 Data 9 decembrie 2016 16:21:00
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <stdio.h>
#include <vector>
#include <cctype>
#include <string.h>

#define BUF_SIZE 1<<17
char buffer[BUF_SIZE];
int pbuf = BUF_SIZE;
FILE *fi, *fo;
inline char nextch(){
    if(pbuf == BUF_SIZE){
        fread(buffer, BUF_SIZE, 1, fi);
        pbuf=0;
    }
    return buffer[pbuf++];
}
inline int nextnum(){
    int a = 0;
    char c = nextch();
    while(!isdigit(c))
        c = nextch();
    while(isdigit(c)){
        a = a*10+c-'0';
        c = nextch();
    }
    return a;
}

#define MAXN 50000

std::vector < int > G[1 + MAXN];
int viz[1 + MAXN];
int st[1 + MAXN], ind;

void dfs(int node){
    if(viz[node]) return ;
    viz[node] = 1;
    for(auto y: G[node])
        dfs(y);
    st[ind++] = node;
}

int main(){
    fi = fopen("sortaret.in","r");
    fo = fopen("sortaret.out","w");

    int n = nextnum(), m = nextnum();
    for(int i = 0; i < m; i++){
        int x = nextnum(), y = nextnum();
        G[x].push_back(y);
    }

    for(int i = 1; i <= n; i++)
        dfs(i);

    for(int i = ind - 1; i >= 0; i--)
        fprintf(fo,"%d ", st[i]);
    fclose(fi);
    fclose(fo);
    return 0;
}