dfsbfs

#include <stdio.h>

#include <stdlib.h>

#include <memory.h>

struct node

{

int w;

int end;

struct node* next;

};

typedef struct node node;

struct heapnode

{

int end;

int val;

};

typedef struct heapnode heapnode;

int queue[1000];

int front;

int tail;

int inqueue(int a)

{

queue[tail++]=a;

return 0;

}

int dequeue()

{

if (front == tail)

return -987654321;

return queue[front++];

}

int pd[100];

int pb[100];

int visited[100];

node* adj;

int v,e;

struct heapnode heap[10000];

int heapsize;

void insert_adj(int a, int b, int w){

node* temp;

node* z;

if (adj[a].end == 0){

adj[a].end=b;

adj[a].w=w;

adj[a].next=NULL;

return;}

temp=&adj[a];

while(temp->next != NULL){

temp=temp->next;}

z=(node*) malloc(sizeof(node));

z->end=b;

z->w=w;

z->next=NULL;

temp->next=z;

}

void dfs(int i)

{

if (visited[i] != -1)

return;

else

{

node* t=&adj[i];

visited[i]=1;

while( t!=NULL &&t->end != 0 )

{

if (visited[t->end] == -1){

pd[t->end]=i;

dfs(t->end);

}

t=t->next;

}

}

}

void bfs(int i)

{

int z = dequeue();

while( z!=-987654321)

{

node* t = &adj[z];

while(t!=NULL &&t->end != 0)

{

if (visited[ t->end] == -1)

{

visited[t->end] = 0;

pb[t->end] = z;

inqueue(t->end);

}

t=t->next;

}

visited[z] = 1;

z=dequeue();

}

}

int main(void)

{

int i,sum=0;

int a,b,w=0;

FILE* fin = fopen("input.txt","r");

node* t;

fscanf (fin,"%d %d",&v,&e);

adj = (node*)malloc(sizeof(node)*(v+1));

for (i=0;i<=v;i++){

adj[i].end=0;

adj[i].w=0;

adj[i].next=NULL;

}

for (i=0;i<e;i++)

{

fscanf (fin,"%d %d",&a,&b);

insert_adj(a,b,w);

//insert_adj(b,a,w);

}

memset(visited,-1,sizeof(visited));

memset(pd,-1,sizeof(pd));

memset(pb,-1,sizeof(pb));

for (int i=1;i<=v;i++)

{

if (visited[i]==-1)

dfs(i);

}

memset(visited,-1,sizeof(visited));

for (int i=1;i<=v;i++)

{

if (visited[i]==-1){

inqueue(i);

bfs(i);

}

}

for (i=1;i<=v;i++)

{

printf ("%d ",pd[i]);

}

printf ("\n");

for (i=1;i<=v;i++)

{

printf ("%d ",pb[i]);

}

printf ("\n");

return 0;

}