Cod sursa(job #2204968)

Utilizator bodea.georgianaBodea Georgiana bodea.georgiana Data 17 mai 2018 13:34:25
Problema Sortare topologica Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.94 kb
#include <stdio.h>
#include <bitset>
#include <deque>

using namespace std;
FILE *f,*g;
int m,n;
int start[50002],t[2][100002];
bitset <50002> viz;
deque <int> q;

void df(int nod);
void noduri();

int main()
{
    int x,y,i,k;
    f=fopen("sortaret.in","r");
    g=fopen("sortaret.out","w");
    fscanf(f,"%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        fscanf(f,"%d %d",&x,&y);
        ++k;
        t[0][k]=y;
        t[1][k]=start[x];
        start[x]=k;
    }
    noduri();
    while(!q.empty())
    {
        k=q.back();
        fprintf(g,"%d ",k);
        q.pop_back();
    }
    fclose(f);
    fclose(g);
    return 0;
}

void df(int nod)
{
    int no;
    no=start[nod];
    while(no)
    {
        if(!viz[t[0][no]])
            df(t[0][no]);
        no=t[1][no];
    }
    q.push_back(nod);
    viz[nod]=1;
}

void noduri()
{
    for(int i=1;i<=n;++i)
        if(!viz[i])
            df(i);
}