#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>



#define type int
int mat[100][100];
int visited[100];

typedef struct listNode
{
	type element;
	type element2;
	listNode* next;
	listNode* prev;
};




void pushStiva(listNode*& head, type element)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->element = element;
	node->next = NULL;
	node->prev = head;

	if (head == NULL)
	{
		head = node;
		return;
	}
	head->next = node;
	head = head->next;
	head->next = NULL;
}
void popStiva(listNode*& head)
{
	if (head == NULL)
		return;
	listNode* aux = head;
	head = head->prev;
	if(head!=NULL)
	head->next = NULL;
	free(aux);
}

int citireFisierMatAdiacenta(char *filename)
{
	FILE* fin = fopen(filename, "r");
	if (fin == NULL)
	{
		exit(0);
	}

	int noduri, muchii;
	fscanf(fin, "%d%d", &noduri, &muchii);
	int n, m;
	for(int i=0;i<muchii;i++)
	{
		fscanf(fin, "%d%d", &m, &n);
		mat[n][m] = mat[m][n] = 1;
	}
	return noduri;
}

void pushCoada(listNode*& first, listNode*& last, type element)
{
	listNode* node = (listNode*)malloc(sizeof(listNode));
	node->element = element;
	node->next = NULL;
	node->prev = last;
	if (last == NULL)
	{
		last = node;
		first = node;
		return;
	}

	last->next = node;
	last = last->next;
}
void popCoada(listNode*& first, listNode*& last)
{
	if (first == NULL)
		return;
	if (first->next == NULL)
	{
		free(first);
		first = NULL;
		last = NULL;
		return;
	}
	listNode* aux = first;
	first = first->next;
	first->prev = NULL;
	free(aux);
}
void BFS_coada(listNode*&first,listNode*&last,int noduri,type element)
{
	pushCoada(first,last,element);
	while (first != NULL)
	{
		visited[first->element]=1;
		for (int i = 1; i <= noduri; i++)
		{
			if (mat[i][first->element] && visited[i]==0)
			{
				pushCoada(first,last, i);
				visited[i] = 1;
			}
		}
		printf("%d ", first->element);
		popCoada(first, last);
	}
	for (int i = 1; i <= noduri; i++)
	{
		if (visited[i] == 0)
			BFS_coada(first,last, noduri, i);
	}
}

void afisareMatriceAdiacente(int noduri)
{
	for (int i = 1; i <= noduri; i++)
	{
		for (int j = 1; j <= noduri; j++)
		{
			printf("%d ", mat[i][j]);
		}
		printf("\n");
	}
}

void DFS_stiva(listNode *&stiva,int noduri,int element)
{
	
	pushStiva(stiva, element);
	printf("%d ", stiva->element);
	while (stiva != NULL)
	{
		visited[stiva->element] = 1;
		for (int i = 1; i <= noduri; i++)
		{
			if (mat[i][stiva->element] && visited[i]==0)
			{
				visited[i] = 1; 
				pushStiva(stiva,i);
				printf("%d ", stiva->element);
				i = 1;
			}
		}
		popStiva(stiva);
	}
	for (int i = 1; i < noduri; i++)
	{
		if (visited[i] == 0)
		{
			printf("\nGraful nu este conex: ");
			DFS_stiva(stiva, noduri, i);
		}
	}
}
void visitedReConfig(int noduri)
{
	for (int i = 1; i <= noduri; i++)
		visited[i] = 0;
}



int main()
{
	int noduri = citireFisierMatAdiacenta((char*)"muchii.txt");
	
	listNode* head = NULL;
	listNode* first = NULL, * last = NULL;
	BFS_coada(first,last, noduri,1);
	visitedReConfig(noduri);
	printf("\n");
	DFS_stiva(head, noduri, 1);
	printf("\n");
}