백준 11724번 연결 요소의 개수

첫번째 코드

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

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

int Found[1001];//탐색된 숫자는 1 저장

Node* array[1001];//그래프
Node* brray[1001];//그래프의 마지막 노드의 주소

Node arr[1001];

void DFS(int x)//탐색을 시작하는 숫자 x
{
	Node* cur = array[x]->next;

	Found[x] = 1;

	while (cur != NULL)
	{
		if (Found[cur->data] == 0)
		{
			DFS(cur->data);
		}
		cur = cur->next;
	}

	return;
}

int main()
{
	int i, N, M;
	int x, y;
	int count = 0;
	Node* cur;

	scanf("%d %d", &N, &M);

	for (i = 1; i <= N; i++)
	{
		brray[i] = array[i] = arr + i;
	}

	for (i = 0; i < M; i++)//그래프 만들기
	{
		scanf("%d %d", &x, &y);

		cur = brray[x];
		cur->next = malloc(sizeof(Node));
		cur->next->data = y;
		brray[x] = cur->next;
		brray[x]->next = NULL;

		cur = brray[y];
		cur->next = malloc(sizeof(Node));
		cur->next->data = x;
		brray[y] = cur->next;
		brray[y]->next = NULL;
	}

	for (i = 1; i <= N; i++)
	{
		if (Found[i] == 0)
		{
			DFS(i);
			count++;
		}
	}

	printf("%d", count);
	return 0;
}

그리고 그래프를 계속 연결리스트로 그려서 오래 걸리나 싶어서 배열로 구현해보기로 했다.

두번째 코드

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

char Found[1001];//탐색된 숫자는 1 저장

int array[1001][1001];//그래프
int arr[1001];//현재 저장된 노드의 개수 저장

void DFS(int x)//탐색을 시작하는 숫자 x
{
	int i;

	Found[x] = 1;

	for (i = 0; i < arr[x]; i++)
	{
		if (Found[array[x][i]] == 0)
		{
			DFS(array[x][i]);
		}
	}
	
	return;
}

int main()
{
	int i, N, M;
	int x, y;
	int count = 0;

	scanf("%d %d", &N, &M);

	for (i = 0; i < M; i++)//그래프 만들기
	{
		scanf("%d %d", &x, &y);

		array[x][arr[x]++] = y;
		array[y][arr[y]++] = x;
	}

	for (i = 1; i <= N; i++)
	{
		if (Found[i] == 0)
		{
			DFS(i);
			count++;
		}
	}

	printf("%d", count);
	return 0;
}