Cod sursa(job #2204945)

Utilizator BogdanAlexandruBogdan-Alexandru Dig BogdanAlexandru Data 17 mai 2018 12:42:51
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.89 kb
#include <stdio.h>
#include <deque>
using namespace std;
FILE *f,*g;
deque<int> coada;
int t[2][2*100000+2],start[50005],fr[50005];
void DFS(int nod)
{
    int i;
    fr[nod]=1;
    i=start[nod];
    while(i)
    {
        if(!fr[t[0][i]])
            DFS(t[0][i]);
        i=t[1][i];
    }
    coada.push_back(nod);
}
void Solve(int n)
{
    int i;
    for(i=1;i<=n;i++)
        if(!fr[i])DFS(i);
}
void Afisare(int n)
{
    int i;
    for(i=1;i<=n;i++)
    {
        fprintf(g,"%d ",coada.back());
        coada.pop_back();
    }
}
int main()
{
    f=fopen("sortaret.in","r");g=fopen("sortaret.out","w");
    int n,m,i,j,k=0,x,y;
    fscanf(f,"%d %d\n",&n,&m);
    for(i=1;i<=n;i++)
    {
        fscanf(f,"%d %d",&x,&y);
        ++k;
        t[0][k]=y,t[1][k]=start[x];
        start[x]=k;
    }
    Solve(n);Afisare(n);
    fclose(f),fclose(g);
    return 0;
}