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

//ADJACENCY MATRIX
typedef struct graphMatrix {
	int** adjacencyMatrix;
	int numNodes;
} graphMatrix;

//EDGES
typedef struct edge {
	int leftNode;
	int rightNode;
} edge;

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

//POINTERS/VERTEX
typedef struct vertex {
	int name;
	struct vertex** neighbors;
	int numNeighbors;
	//	int* weights;
} vertex;

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

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 queue[100];
int indexQueue = 0;

void Qpush(int value)
{
	if (indexQueue < 100)
		queue[indexQueue++] = value;
	else
		printf("Dimensiune coada depasita!\n");
}

int Qpop()
{
	//verificare daca sunt elemente in coada
	if (indexQueue > 0) {
		int value = queue[0];
		for (int i = 0; i < indexQueue - 1; i++) {
			queue[i] = queue[i + 1];
		}
		queue[indexQueue--] = 0;
		return value;
	}
	printf("Coada este goala!\n");
	return (int)0;
}

void dfs_vertex(graphVertex graph, int currentNode, int* visited)
{
	visited[currentNode] = 1;
	//printf("%d ", currentNode);
	for (int j = 0; j < graph.nodes[currentNode].numNeighbors; j++) {
		if (visited[graph.nodes[currentNode].neighbors[j]->name] == 0) {
			dfs_vertex(graph, graph.nodes[currentNode].neighbors[j]->name, visited);
		}
	}
}

graphVertex readGraphVertex(const char* fileName)
{
	graphVertex graph;
	graph.numEdges = 0;
	graph.numNodes = 0;
	FILE* f = fopen(fileName, "r");
	if (f == NULL)
		return graph;

	fscanf(f, "%i%i", &(graph.numNodes), &(graph.numEdges));
	graph.nodes = (vertex*)malloc(sizeof(vertex) * graph.numNodes);
	if (graph.nodes == NULL)
		return graph;
	for (int i = 0; i < graph.numNodes; i++) {
		graph.nodes[i].name = i;
		graph.nodes[i].numNeighbors = 0;
		graph.nodes[i].neighbors = NULL;
	}
	int left, right;
	for (int i = 0; i < graph.numEdges; i++) {
		fscanf(f, "%d %d", &left, &right);
		graph.nodes[left].numNeighbors++;
		graph.nodes[left].neighbors = (vertex**)realloc(graph.nodes[left].neighbors, sizeof(vertex*) * graph.nodes[left].numNeighbors);
		graph.nodes[left].neighbors[graph.nodes[left].numNeighbors - 1] = &graph.nodes[right];
	}
	fclose(f);
	return graph;
}

int main()
{
	//POINTERS/VERTEX
	graphVertex graphV = readGraphVertex("dfs.in");

	int visited[100000] = {0};  //we assume fewer than 100 nodes
	int count = 0;

	for (int i = 0; i < graphV.numNodes; i++) {
		if (visited[i] == 0) {
			count++;
			dfs_vertex(graphV, i, visited);
		}
	}

	printf("*** Result: %d ***\n", count);

	return 0;
}