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

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

static int *components(Graph g);
static void dfs(Graph g, Vertex v, int componentNo, int *componentOf);

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 *componentOf = malloc(g->nV * sizeof(int));
	for (int i = 0; i < g->nV; i++) {
		componentOf[i] = -1;
	}

	int componentNo = 0;
	for (Vertex v = 0; v < g->nV; v++) {
		if (componentOf[v] == -1) {
			dfs(g, v, componentNo, componentOf);
			componentNo++;
		}
	}

	return componentOf;
}

static void dfs(Graph g, Vertex v, int componentNo, int *componentOf) {
	componentOf[v] = componentNo;

	struct adjNode *curr = g->edges[v];
	for (; curr != NULL; curr = curr->next) {
		Vertex w = curr->v;
		if (componentOf[w] == -1) {
			dfs(g, w, componentNo, componentOf);
		}
	}
}