Implementation (Part 1)

Coddy의 크루스칼 알고리즘 - 그래프 알고리즘 코스 레슨 — 9개 중 5번째.

사이클 감지 엔진인 유니온 파인드(union-find)부터 시작합니다.

챌린지

중급

Kruskal의 사이클 테스트는 union-find에 의존합니다. 먼저 이를 사용하여 연결된 컴포넌트(connected components)의 개수를 세는 기능을 구현해 보겠습니다.

n과 평면화된 edges 배열(무방향 그래프의 [u, v, w, ...] 트리플 구조; 여기서는 가중치 w를 무시함)을 인자로 받아 union-find를 사용하여 계산된 연결된 컴포넌트의 개수를 반환하는 countSets 함수를 작성하세요.

예를 들어, 4개의 정점과 [0,1,5, 2,3,5]라는 간선이 있다면 {0,1}과 {2,3}이라는 2개의 컴포넌트가 존재합니다.

직접 해보기

#include <stdlib.h>

int countSets(int n, int* edges, int edges_size) {
    // 여기에 코드를 작성하세요
    return 0;
}

실력 점검

이 레슨에는 짧은 퀴즈가 포함되어 있습니다. 레슨을 시작해 문제를 풀고 진행 상황을 기록하세요.

크루스칼 알고리즘 - 그래프 알고리즘의 모든 레슨

1Introduction

2The Algorithm

3Final Challenges