💡 그래프 이론/그래프 탐색/너비 우선 탐색/깊이 우선 탐색
Memory 5028KB Time 128ms Code Length 524B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<stdio.h>
int point[1001][1001];
int visited[1001];
int cnt = 0;
int n, m;
void dfs(int node) {
for (int i = 1; i <= n; i++) {
if (point[node][i] == 1) {
if (visited[i] == 1) continue;
visited[i] = 1;
dfs(i);
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 0; i < m; i++) {
int left, right;
scanf(" %d %d", &left, &right);
point[left][right] = 1;
point[right][left] = 1;
}
for (int i = 1; i <= n; i++) {
if (visited[i] == 1) continue;
dfs(i);
cnt++;
}
printf("%d",cnt);
}
이 코드는 입력으로 받은 그래프의 연결 요소의 개수를 구하는 프로그램이다.
입력으로 노드의 개수(n)와 간선의 개수(m)를 받는다.
이어지는 m개의 줄에는 간선의 정보가 주어지고, 해당 간선으로 노드들을 연결한다.
방문 여부를 나타내는 visited 배열을 초기화하고, 모든 노드에 대해 방문하지 않은 경우에 대해 dfs 함수를 호출한다.
dfs 함수는 해당 노드와 연결된 모든 노드를 재귀적으로 방문하며 visited 배열을 업데이트한다.
한 연결 요소에 대한 탐색이 끝나면 연결 요소의 개수(cnt)를 증가시킨다.
모든 노드를 방문할 때까지 3~5과정을 반복하고, 최종적으로 연결 요소의 개수를 출력한다.
