#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;

int stack[100];
int indexStack = 0;

void push(int value)
{
	if (indexStack < 100)
		stack[indexStack++] = value;
	else
		printf("Dimensiune stiva depasita!\n");
}

int pop()
{
	// verificare daca sunt elemente in stiva
	if (indexStack > 0) {
		int value = stack[--indexStack];
		stack[indexStack] = 0;
		return value;
	}
	printf("Stiva este goala!\n");
	return (int)0;
}
int pop_coada()
{
	if (indexStack > 0) {
		int value = stack[0];
		for (int i = 0; i < indexStack - 1; i++)
			stack[i] = stack[i + 1];
		stack[indexStack] = 0;
		indexStack--;
		return value;
	}
	printf("Coada este goala!\n");
	return (int)0;
}
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;
	push(currentNode);
	visited[currentNode] = 1;
	while (indexStack > 0) {
		int j = pop();
		for (int i = 0; i < graph.numEdges; i++)
			if (j == graph.edges[i].leftNode && visited[graph.edges[i].rightNode] == 0) {
				push(graph.edges[i].rightNode);
				visited[graph.edges[i].rightNode] = 1;
				break;
			}
		if (indexStack == 0) {
			for (int i = 0; i < graph.numEdges; i++)
				if (visited[graph.edges[i].rightNode] == 0) {
					push(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.txt");
	// printEdges(newGraph);
	int visited[100] = {0};
	int nr_comp = dfs_edges(newGraph, 1, visited);
	FILE* f = fopen("dfs.out.txt", "w");
	if (f == NULL)
		exit(-1);
	fprintf(f, "%d", nr_comp);
	fclose(f);
	return 0;
}