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

#define type int

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

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);
}




listNode* graph[1000];
void insertNodeInGraph(int graphNo,type element)
{
	listNode* p=graph[graphNo];
	if(p==NULL)
		pushCoada(graph[graphNo], p, element);
	else
	{
		while (p->next != NULL)
			p = p->next;
		pushCoada(graph[graphNo], p, element);
	}
}

int n,m, visited[1000];
void readGraph(char* filename)
{
	FILE* fin = fopen(filename, "r");
	
	fscanf(fin, "%d%d", &n, &m);
	int x, y;

	for (int i = 1; i <= n; i++)
	{
		graph[i] = NULL;
	}
	for(int i = 1; i <= m; i++)
	{
		fscanf(fin, "%d%d", &x, &y);
		insertNodeInGraph(x, y);
	}
}

void PrintGraph()
{
	int ok = 0;
	for (int i = 1; i <= n; i++)
	{
		if (graph[i] != NULL)
		{
			ok++;
			printf("%d ", i);
		}
		while (graph[i] != NULL)
		{
			printf("%d ", graph[i]->element);
			graph[i] = graph[i]->next;
		}
		if (ok)
			printf("\n");
		ok = 0;
	}
}
void BFS_recursiv(int i)
{
	listNode* p;

	printf("%d ", i);
	p = graph[i];
	visited[i] = 1;
	while (p != NULL)
	{
		i = p->element;

		if (!visited[i])
			BFS_recursiv(i);
		p = p->next;
	}
}
int main()
{
	readGraph((char*)"bfs.in");
	//PrintGraph();
	int conexe = 0;
	for(int i=1;i<=n;i++)
		if (visited[i] == 0)
		{
			conexe++;
			BFS_recursiv(i);
		}
	printf(" Numarul de elemente conexe: %d ",conexe);
}