Cod sursa(job #2707251)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 16 februarie 2021 18:38:23
Problema Sortare topologica Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
//Ilie Dumitru
#include<cstdio>

struct nod
{
    int x;
    nod *next;
};

nod *arce[50000];
int N, M, top[50000], last;
char verif[6250];

void setbit(int i){verif[i>>3]|=1<<(i&7);}
char getbit(int i){return verif[i>>3]&(1<<(i&7));}

void add(int x, int y)
{
    nod *n=new nod;
    n->x=y;
    n->next=arce[x];
    arce[x]=n;
}

void sortare_topologica(int i)
{
    nod *n;
    int x;
    for(n=arce[i];n;n=n->next)
    {
        x=n->x;
        if(!getbit(x))
        {
            setbit(x);
            sortare_topologica(x);
        }
    }
    top[last--]=i;
}

int main()
{
    freopen("sortaret.in", "r", stdin);
    freopen("sortaret.out", "w", stdout);
    int i, a, b;
    scanf("%i", &N);
    scanf("%i", &M);
    for(i=0;i<M;++i)
    {
        scanf("%i", &a);
        scanf("%i", &b);
        add(a-1, b-1);
    }
    fclose(stdin);
    last=N-1;
    for(i=0;i<N;++i)
        if(!getbit(i))
        {
            setbit(i);
            sortare_topologica(i);
        }
    for(i=0;i<N;++i)
        printf("%i ", top[i]+1);
    fclose(stdout);
    return 0;
}