Cod sursa(job #793238)

Utilizator legendary28Cornescu Mihail legendary28 Data 2 octombrie 2012 13:09:05
Problema Sortare topologica Scor 40
Compilator c Status done
Runda Arhiva educationala Marime 2.64 kb
#include<stdio.h>
#include<stdlib.h>
#define maxV 5010

typedef struct nod
{
    int vertex;
    struct nod *next;
}Node;

Node **node;
int N,M,S[maxV],i,j,l,ok,n,m;
Node *primL,*p,*q;

void initial(void)
{
    node = (Node **)malloc(maxV * sizeof(Node *));
    for(i=1;i<=N;i++)
    {
        node[i]=malloc(sizeof(Node));
        node[i]->next=NULL;
    }
}

void CreateAdjList(void)
{
    int v1,v2;
    Node *p;

    for(i=1;i<=M;i++)
    {
        p=malloc(sizeof(Node));
        scanf("%d%d",&v1,&v2);

        p->vertex=v2;
        p->next=node[v1]->next;
        node[v1]->next=p;
    }

}

void printS()
{
    printf("S: ");
    for(i=1;i<=l;i++)
        printf("%d ",S[i]);
    printf("\n");
}

void printL()
{
    printf("L: ");
    for(p=primL->next;p;p=p->next)
        printf("%d ",p->vertex);
    printf("\n");
}

void addS()
{
    Node *p;
    for(i=1;i<=N;i++)
    {
        ok=0;
        for(j=1;j<=N;j++)
        {
            p=node[j]->next;
            while(p)
            {
                if(p->vertex==i) ok=1;
                p=p->next;
            }
        }
        if(!ok) S[++l]=i;
    }
}

Node *createL()
{
    Node *primL;
    primL=malloc(sizeof(Node));
    primL->vertex=S[1];
    primL->next=NULL;
    return primL;
}

void addL(int a)
{
    p=primL;
    for(p=primL;p->next;p=p->next)
        ;
    q=malloc(sizeof(Node*));
    q->vertex=a;
    q->next=NULL;
    p->next=q;
    p=q;

}

void elimina(Node *q)
{
    node[n]->next=q->next;
    q=node[n]->next;
}

void S_Topologica()
{
    p=primL;
    while(l)
    {

        n=S[l--];
        addL(n);
        p=node[n]->next;
        for(p=node[n]->next;p;p=p->next)
        {
            m=p->vertex;
            elimina(p);
            ok=0;
            for(i=1;i<=N;i++)
                if(i!=m)
                {
                    for(q=node[i]->next;q;q=q->next)
                        if(q->vertex==m) ok=1;
                }
            if(!ok) S[++l]=m;
        }
    }
}

void printList()
{
    int i;
    Node *p;
    printf("\n");
    for(i=1;i<=N;i++)
    {
        printf("    %d: ",i);
        p=node[i]->next;
        while(p)
        {
            printf("%d ",p->vertex);
            p=p->next;
        }
        printf("\n");
    }
}


int main()
{
    freopen("sortaret.in","r",stdin);
    freopen("sortaret.out","w",stdout);

    scanf("%d%d",&N,&M);

    initial();
    CreateAdjList();
    addS();
    primL=createL();
    S_Topologica();
    for(p=primL->next;p;p=p->next)
        printf("%d ",p->vertex);
    return 0;
}