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

typedef struct vertex {
	int name;
	struct vertex** neighbors;
	int numNeighbors;
} vertex;

typedef struct graphVertex {
	int numNodes;
	int numEdges;
	vertex** nodes;
} graphVertex;

typedef struct node
{
	int element;
	struct node* next;
} listNode;

void insertNodeHeadOfList(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->element = element;
	*listStart = node;
}
listNode* getNode(listNode* listNode, int poz)
{
	for (int i = 0; i < poz; i++)
	{
		listNode = listNode->next;
		if (listNode->next == NULL)
			break;
	}
	return listNode;
}
void insertNodeInList(listNode** listStart, int element, int poz)
{
	if (poz == 0)
	{
		insertNodeHeadOfList(listStart, element);
		return;
	}
	listNode* node = (listNode*)malloc(sizeof(listNode));
	if (node == NULL)
	{
		printf("ERROR: CAN NOT ALLOCATE RAM\n");
		return;
	}

	listNode* aux = getNode(*listStart, poz - 1);

	node->next = aux->next;
	node->element = element;
	aux->next = node;
}
void push(listNode** listStart, int element)
{
	listNode* copie = *listStart;
	int poz = 0;

	if (copie == NULL)
		insertNodeHeadOfList(listStart, element);
	else
	{
		while (copie != NULL)
		{
			copie = copie->next;
			poz++;
		}

		insertNodeInList(listStart, element, poz);
	}
}
int pop(listNode** listStart)
{
	if (*listStart == NULL)
		return;
	listNode* aux = (*listStart);
	int value = aux->element;
	*listStart = (*listStart)->next;
	return value;
}

vertex* vecin(graphVertex* graph, int val)
{
	for (int i = 1; i <= graph->numNodes; i++)
		if (graph->nodes[i]->name == val)
			return graph->nodes[i];

}
graphVertex* readGraph(char* filename)
{

	FILE* f = fopen(filename, "r");
	if (f == NULL)
	{
		printf("Eroare deschidere fisier");
		exit(1);
	}

	graphVertex* graph = (graphVertex*)malloc(sizeof(graphVertex));

	fscanf(f, "%d%d", &(graph->numNodes), &(graph->numEdges));

	graph->nodes = (vertex**)malloc(sizeof(vertex*) * (graph->numNodes + 1));
	if (graph->nodes == NULL)
		return graph;

	for (int i = 0; i <= graph->numNodes; i++) {
		graph->nodes[i] = (vertex*)malloc(sizeof(vertex));
		graph->nodes[i]->name = i;
		graph->nodes[i]->numNeighbors = 0;
		graph->nodes[i]->neighbors = NULL;
	}

	int y, z;

	for (int i = 1; i <= graph->numNodes; i++)
	{
		fseek(f, 0, SEEK_SET);
		fscanf(f, "%d%d", &y, &z);
		for (int j = 0; j < graph->numEdges; j++)
		{
			fscanf(f, "%d%d", &y, &z);
			if (y == i && y != z)
				graph->nodes[i]->numNeighbors++;
			if (z == i && y != z)
				graph->nodes[i]->numNeighbors++;
		}
	}
	
	for (int i = 0; i <= graph->numNodes; i++)
		graph->nodes[i]->neighbors = (vertex**)malloc(sizeof(vertex*) * (graph->nodes[i]->numNeighbors + 1));


	for (int i = 1; i <= graph->numNodes; i++)
	{
		int j = 1;
		fseek(f, 0, SEEK_SET);
		fscanf(f, "%d%d", &y, &z);
		for (int k = 0; k < graph->numEdges; k++)
		{
			fscanf(f, "%d%d", &y, &z);
			if (y == i && y != z)
			{
				graph->nodes[i]->neighbors[j] = vecin(graph, z);
				j++;
			}
			if (z == i && y != z)
			{
				graph->nodes[i]->neighbors[j] = vecin(graph, y);
				j++;
			}
		}
	}


	fclose(f);
	return graph;
}

void DFS(graphVertex* graph,int currentNode, int* visited)
{
	visited[currentNode] = 1;
	for (int j = 1; j <= graph->nodes[currentNode]->numNeighbors; j++)
	{
		if (!visited[graph->nodes[currentNode]->neighbors[j]->name])
			DFS(graph, graph->nodes[currentNode]->neighbors[j]->name, visited);
	}
}

int main()
{
	graphVertex* graph = readGraph("dfs.in");
	int* visited = (int*)calloc(graph->numNodes+1,sizeof(int));
	int ct = 0;

	for (int i = 1; i <= graph->numNodes; i++)
		if(visited[i]==0)
		{
			ct++;
			DFS(graph, i, visited);
		}

	FILE* fout = fopen("dfs.out", "w");
	fprintf(fout, "%d", ct);
	fclose(fout);

	return 0;
}