Time limit: 500ms
Memory limit: 256mb

Description:
Input a directed graph with sorted nodes, output its DFS sequence. Note that the nodes with smaller IDs should be output first.


-------------------------Copy the following code, complete it and submit-------------------------


/*
I, , am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<string.h>


typedef struct stack
{
	int *arr;
	int capacity;
	int top;
}Stack;

Stack* createStack(int capacity)
{
	Stack* S = (Stack *)malloc(sizeof(struct stack));
	S->arr = (int*)malloc(sizeof(int) * capacity);
	S->capacity = capacity;
	S->top = 0;
	return S;
}

void destoryStack(Stack *S)
{
	free(S->arr);
	free(S);
	return;
}

int isFull(Stack *S)
{
	return S->top == S->capacity;
}

int isEmpty(Stack *S)
{
	return S->top == 0;
}

int push(Stack *S, int e)
{
	if (isFull(S))
		{
			printf("stack overflow!");
			return -1;
		}
	else
		{
			S->arr[S->top] = e;
			S->top++;
			return 1;
		}
}

int pop(Stack *S)
{
	if (isEmpty(S))
		{
			printf("stack underflow!");
			return -1;
		}
	else
		{
			S->top --;
			int e = S->arr[S->top];
			return e;
		}
}

int top(Stack *S)
{
	if (isEmpty(S))
		{
			printf("stack underflow!");
			return -1;
		}
	else
		{
			return S->arr[S->top-1];
		}
}


//Define tuple to record one edge's two vertices
typedef struct tuple
{
	int first;
	int second;
}Tuple;



void DFS(int n, int source, int* outdegree, int ** outAdjList){
	//Create Stack for DFS
	Stack* S = createStack(n);
	
	//record the color, initialize all entries in color to zeros
	int* color = (int*)malloc(sizeof(int) * n);
	memset(color, 0, n * sizeof(int));
	
	//DFS algorithm starts from source node on directed graph
	
	//number of nodes have been visited
	int n_visit = 1;
	//push the source node
	push(S, source);
	printf("%d -> ", source);
	
	//set the color of the node to 1 (gray)
	color[source] = 1;
	
	while (!isEmpty(S)){
		int v = top(S);
		/* find_white_node is a flag, if we find a white node in v's neighbors
		then set it to 1, else 0 */
		int find_white_node = 0;
		for(int i = 0; i < outdegree[v]; i++)
			{
				/* retrieve the nodes points out from "v",
				so we should use outAdjList */
				int u = outAdjList[v][i];
				if(color[u] == 0)
					{
						push(S, u);
						n_visit++;
						if(n_visit < n)
							{
								printf("%d -> ", u);
							}
						else
							{
								printf("%d \n", u);
							}
						color[u] = 1;
						find_white_node = 1;
						break;
					}
			}
		if(!find_white_node)
			{
				color[v] = 2;
				pop(S);
			}
	}
	
	free(color);
	destoryStack(S);
}

int main(){

	//the number of nodes in the graph
	int n, m;
	int source;
	
	scanf("%d %d %d", &n, &m, &source);
	
	//one edge from "from" points to "to"
	int from;
	int to;
	
	//record the edges by tuple list
	Tuple* edge_vec = (Tuple*)malloc(sizeof(Tuple) * m);
	
	int pointer = 0;
	
	
	for(int i = 0; i < m; i++)
	{
		scanf("%d%d", &from, &to);
		edge_vec[pointer].first = from;
		edge_vec[pointer].second = to;
		pointer++;
	}
	
	// directed, so we need outdegree
	int* outdegree;
	outdegree = (int*)malloc(sizeof(int) * n);
	
	for (int i = 0; i < n; i++)
	{
		outdegree[i] = 0;
	}
	
	for (int i = 0; i < m; i++)
	{
		from = edge_vec[i].first;
		to = edge_vec[i].second;
		/* record outdegree to initialize
		proper space for each node */
		outdegree[from]++;
	}
	
	//create outAdjList
	int ** outAdjList;
	
	//record specific nodes point from the current node
	outAdjList = (int**)malloc(sizeof(int*) * n);
	
	//record how many edges have pointed out from the current nodes
	int *pointer_out = (int*)malloc(sizeof(int) * n);
	
	for (int i = 0; i < n; i++)
	{
		outAdjList[i] = (int*)malloc(sizeof(int) * outdegree[i]);
	}
	

	for (int i = 0; i < n; i++)
	{
		pointer_out[i] = 0;
	}
	
	for (int i = 0; i < m; i++)
	{
		from = edge_vec[i].first;
		to = edge_vec[i].second;
		/* "from" is the node where the edge starts from
		so it's outAdjList */
		outAdjList[from][pointer_out[from]] = to;
		pointer_out[from]++;
	}
	
	DFS(n, source, outdegree, outAdjList);
	
	return 0;
}












-------------------------------------------End of Code-------------------------------------------

Input:
The number of nodes.
The number of edges.
The source node.
Edges of the directed graph given in sorted order.

Output:
The DFS sequence of the graph. IDs in the DFS should be output in the sorted order.

Sample Input 1:
8 10 0
0 1
0 2
1 3
1 4
3 7
4 7
2 5
2 6
5 7
6 7


Sample Output 1:
0 -> 1 -> 3 -> 7 -> 4 -> 2 -> 5 -> 6