Cod sursa(job #918316)

Utilizator alexandrul_21Niculescu Mihai alexandrul_21 Data 18 martie 2013 19:59:15
Problema Sortare topologica Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <stdio.h>
#define MAX_N 50000
#define INF 2000000000
using namespace std;
struct nod
{
    int nr;
    nod *next;
}*First[MAX_N];
int N,M,Grad[MAX_N],Start,Visited[MAX_N];
void Insert(int x,int y)
{
    nod *q=new nod;
    q->nr=y;
    q->next=First[x];
    First[x]=q;
}
void Read()
{
    freopen("sortaret.in","r",stdin);
    scanf("%d %d\n",&N,&M);
    int i,x,y;
    Grad[0]=INF;
    for(i=1;i<=M;i++)
    {

        scanf("%d %d\n",&x,&y);
        Insert(x,y);
        Grad[y]++;
    }
    for(i=1;i<=N;i++)
    {
        if(Grad[Start]>Grad[i])
            Start=i;
    }
    fclose(stdin);
}
void DF(int k)
{
    nod *q;
    for(q=First[k];q;q=q->next)
    {
        if(Visited[q->nr]==0)
            DF(q->nr);
    }
    Insert(0,k);
}
void Write(nod *p)
{
    if(p)
    {
        printf("%d ",p->nr);
        Write(p->next);
    }
    else
        printf("\n");
}
int main()
{
    Read();
    DF(Start);
    freopen("sortaret.out","w",stdout);
    Write(First[0]);
    fclose(stdout);
    return 0;
}