# Answers for "bottom of the graph solution"

0

bottom of the graph solution

``````# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define MAXV 5001

int N, M;
int order[MAXV];
int visited[MAXV];
int ans[MAXV], cnt, tmp[MAXV], cc;
int no;

typedef struct node
{
struct node *next;
}EdgeNode;
typedef struct vnode
{
EdgeNode *firstedge;
}VertexNode;
typedef struct ALGraph
{
}Graphic;

Graphic GA, GB;
void insert(int u, int v)
{
EdgeNode *s;

s = (EdgeNode *)malloc(sizeof(EdgeNode));
s = (EdgeNode *)malloc(sizeof(EdgeNode));
}

void input()
{
int u, v, i;

for(i = 0; i < M; i++)
{
scanf("%d%d",&u,&v);
insert(u-1,v-1);
}
}

void init()
{
int i;

scanf("%d",&M);
for(i = 0; i < N; i++)
{
}
}

void dfs_b(int v)
{
EdgeNode *s;

visited[v] = 1;
while(s)
{
s = s->next;
}
order[cnt++] = v;
}

void dfs_a(int v)
{
EdgeNode *s;

visited[v] = no;
tmp[cc++] = v;
while(s)
{
{
}
s = s->next;
}
}

int cmp(const void *a,const void *b)
{
int *aa = (int *)a;
int *bb = (int *)b;

return (*aa)-(*bb);
}

void solve()
{
int i, j;
int error;
EdgeNode *s;

cnt = 0;
memset(visited,0,sizeof(visited));
for(i = 0; i < N; i++)
if(!visited[i])
dfs_b(i);
cnt = 0;
memset(visited,0,sizeof(visited));
no = 1;
for(i = N-1; i >= 0; i--)
{
if(!visited[order[i]])
{
cc = 0;
dfs_a(order[i]);
error = 0;
for(j = 0; j < cc; j++)
{
while(s)
{
{
error = 1;
break;
}
s = s->next;
}
}
if(!error)
{
for(j = 0; j < cc; j++)
{
ans[cnt++] = tmp[j];
}
}
no++;
}
}
qsort(ans,cnt,sizeof(ans[0]),cmp);
for(i = 0; i < cnt; i++)
{
printf("%d ",ans[i]+1);
}
printf("\n");
}

int main()
{
while(scanf("%d",&N)==1,N)
{
init();
input();
solve();
}
return 1;
}``````
Posted by: Guest on December-25-2020