[BOJ 11724] 연결 요소의 개수 in C

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

#define MAX_V 1001

typedef struct node {
	int vertex;
	struct node* next;
}Node;

typedef struct graph {
	int numVertex;
	Node** adjList;
}Graph;

typedef struct queue {
	Node* head;
	Node* tail;
	int size;
}Queue;

Node* createNode(int vertex_id) {
	Node* node = (Node*)malloc(sizeof(Node));
	node->vertex = vertex_id;
	node->next = NULL;

	return node;
}

Graph* createGraph(int numVertex) {
	Graph* graph = (Graph*)malloc(sizeof(Graph));
	graph->numVertex = numVertex;

	graph->adjList = (Node**)malloc(sizeof(Node*) * numVertex);
	for (int i = 0; i <= numVertex; i++) {
		graph->adjList[i] = NULL;
	}

	return graph;
}

Queue* createQueue() {
	Queue* q = (Queue*)malloc(sizeof(Queue));
	q->head = q->tail = NULL;
	q->size = 0;

	return q;
}

void addEdge(Graph* graph, int src, int dst) {
	Node* node;

	// src -> dst
	node = createNode(dst);
	node->next = graph->adjList[src];
	graph->adjList[src] = node;

	// dst -> src
	node = createNode(src);
	node->next = graph->adjList[dst];
	graph->adjList[dst] = node;
}

void printGraph(Graph* graph) {
	for (int v = 0; v <= graph->numVertex; v++) {
		Node* cur = graph->adjList[v];
		if (cur == NULL) continue;

		printf("%d: ", v);
		while (cur) {
			printf("%d -> ", cur->vertex);
			cur = cur->next;
		}
		printf("NULL\n");
	}
}

void push(Queue* q, Node* node) {
	if (q->size == 0) {
		q->head = q->tail = node;
	}
	else {
		q->tail->next = node;
		q->tail = node;
	}
	q->size += 1;
}

Node* pop(Queue* q) {
	Node* node = q->head;
	q->size -= 1;
	q->head = q->head->next;
	
	return node;
}

void bfs(Graph* graph, int* visit, int N, int start) {
	Node* cur;
	Node* walk;
	cur = createNode(start);
	Queue* q = createQueue();
	push(q, cur);
	visit[start] = 1;
	
	int v;
	while (q->size > 0) {
		cur = pop(q);
		v = cur->vertex;
		walk = graph->adjList[v];
		while (walk) {
			if (visit[walk->vertex] == 0) {
				visit[walk->vertex] = 1;
				push(q, walk);
			}
			walk = walk->next;
		}
	}

	free(walk);
	free(cur);
	free(q);
}

int main() {
	freopen("input.txt", "r", stdin);
	int N, M, u, v, answer;
	int* visit;
	scanf("%d %d", &N, &M);
	Graph* graph = createGraph(N);
	visit = (int*)calloc(N + 1, sizeof(int));

	for (int i = 0; i < M; i++) {
		scanf("%d %d", &u, &v);
		addEdge(graph, u, v);
	}

	//printGraph(graph);

	answer = 0;
	for (int i = 1; i <= N; i++) {
		if (visit[i] == 0) {
			bfs(graph, visit, N, i);
			answer += 1;
		}
	}
	printf("%d", answer);
	return 0;
}