Cod sursa(job #1882549)

Utilizator miruna999Morarasu Miruna miruna999 Data 17 februarie 2017 12:12:57
Problema Sortare topologica Scor 30
Compilator cpp Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("sortaret.in");
ofstream g("sortaret.out");
struct nod{int nr; nod *urm;}*a[100001];
nod *p;
int n,m,x[50001],j,viz[50001];

void citire()
{
    f>>n>>m;
    int x1,x2;
    for(int i=1;i<=m;i++)
    {
        f>>x1>>x2;
        p=new nod;
        p->nr=x2;
        p->urm=a[x1];
        a[x1]=p;
    }
}

void df(int k)
{
    for(int i=1;i<=n;i++)
        if(i!=k)
        {
            int ok=0,nr=0;
            p=new nod;
            p=a[k];
            while(p)
            {
                nr++;
                if(p->nr==i)
                    ok=1;
                p=p->urm;
            }
            if(ok&&!viz[i])
            {
                p=a[k];
                while(nr>1)
                    nr--,p=p->urm;
                if(p->urm)
                {
                    if(p->urm->urm)
                        p->urm=p->urm->urm;
                }
                else
                    p->urm=NULL;
                df(i);
            }
        }
    x[++j]=k;viz[k]=1;
}

int main()
{
    citire();
    for(int i=1;i<=n;i++)
        if(viz[i]==0)
            df(i);
    for(int i=j;i>=1;i--)
        g<<x[i]<<" ";
    return 0;
}