Pagini recente » Cod sursa (job #2543482) | Cod sursa (job #1695319) | Cod sursa (job #673234) | Cod sursa (job #1024360) | Cod sursa (job #793237)
Cod sursa(job #793237)
#include<stdio.h>
#include<stdlib.h>
#define maxV 100
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;
}