첫번째 코드
#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;
}