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

#include "Graph.h"
#include "GraphPrivate.h"

static int *components(Graph g);
static void dfsComponents(Graph g, Vertex v, int *componentNos, int compNo);

int main(void) {
	Graph g = GraphRead(stdin);
	
	printf("Graph:\n");
	GraphShow(g);

	int *componentOf = components(g);
	for (Vertex v = 0; v < g->nV; v++) {
		printf("componentOf[%d]: %d\n", v, componentOf[v]);
	}

	free(componentOf);
	GraphFree(g);
}

static int *components(Graph g) {
	// TODO
	int *componentNos = malloc(g->nV * sizeof(int));
	for (int i = 0; i < g->nV; ++i) {
		componentNos[i] = -1;
	}

	int compNo = 0;
	for (Vertex v = 0; v < g->nV; ++v) {
		if (componentNos[v] == -1) {
			dfsComponents(g, v, componentNos, compNo);
			compNo++;
		}
	}

	return componentNos;
}

static void dfsComponents(Graph g, Vertex v, int *componentNos, int compNo) {
	componentNos[v] = compNo;
	for (struct adjNode *curr = g->edges[v]; curr != NULL; curr = curr->next) {
		Vertex w = curr->v;
		if (componentNos[w] == -1) {
			dfsComponents(g, w, componentNos, compNo);
		}
	}
}