#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct edge {
	int leftNode;
	int rightNode;
} edge;

typedef struct graphEdges {
	edge *edges;
	int numNodes;
	int numEdges;
} graphEdges;

typedef struct distance {
	int name;
	int distance;
} distance;

typedef struct listNode {
	int name;
	struct listNode *next;
} listNode;

void push(listNode **listStart, int element)
{
	listNode *node = (listNode *)malloc(sizeof(listNode));
	if (node == NULL) {
		printf("ERROR: CAN NOT ALLOCATE RAM\n");
		return;
	}
	node->next = *listStart;
	node->name = element;
	*listStart = node;
}

int pop(listNode **listStart)
{
	listNode *aux = (*listStart);
	int n = aux->name;
	*listStart = (*listStart)->next;
	free(aux);
	return n;
}

graphEdges readGraphEdgeList(const char *fileName)
{
	graphEdges graph;
	graph.numEdges = 0;
	graph.edges = NULL;
	FILE *f = fopen(fileName, "r");
	if (f == NULL)
		return graph;
	char s[10];
	fscanf(f, "%s", s);
	graph.numNodes = atoi(s);
	fscanf(f, "%s", s);
	graph.numEdges = atoi(s);
	graph.edges = (edge *)malloc(graph.numEdges * sizeof(edge));
	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "%s", s);
		graph.edges[i].leftNode = atoi(s);
		fscanf(f, "%s", s);
		graph.edges[i].rightNode = atoi(s);
	}
	fclose(f);
	return graph;
}
int dfs_edges(graphEdges graph, int currentNode, int *visited)
{
	int comp = 1;
	visited = (int *)malloc(graph.numNodes * sizeof(int));
	for (int i = 0; i < graph.numNodes; i++)
		visited[i] = 0;
	listNode *node = NULL;
	push(&node, currentNode);
	visited[currentNode] = 1;
	while (node != NULL) {
		int j = pop(&node);
		for (int i = 0; i < graph.numEdges; i++)
			if (j == graph.edges[i].leftNode && visited[graph.edges[i].rightNode] == 0) {
				push(&node, graph.edges[i].rightNode);
				visited[graph.edges[i].rightNode] = 1;
				break;
			}
		if (node == NULL) {
			for (int i = 0; i < graph.numEdges; i++)
				if (visited[graph.edges[i].rightNode] == 0) {
					push(&node, graph.edges[i].rightNode);
					visited[graph.edges[i].rightNode] = 1;
					comp++;
					break;
				}
		}
	}
	return comp;
}
void printEdges(graphEdges graph)
{
	for (int i = 0; i < graph.numEdges; i++)
		printf("[%d %d]\n", graph.edges[i].leftNode, graph.edges[i].rightNode);
}

int main()
{
	graphEdges newGraph = readGraphEdgeList("dfs.in");
	// printEdges(newGraph);
	int *visited = NULL;
	int nr_comp = dfs_edges(newGraph, 1, visited);
	FILE *f = fopen("dfs.out", "w");
	if (f == NULL)
		exit(-1);
	fprintf(f, "%d", nr_comp);
	fclose(f);
	return 0;
}