블로그 이사 중입니다 >> gumgood.github.io

11724 연결 요소의 개수 본문

Problem Solving/문제 풀이

11724 연결 요소의 개수

gumgood 2018. 2. 5. 09:48

C++11 DFS

C++11 Disjoint set


요소(Component) : 원 그래프 G에서 node와 edge가 서로 겹치지 않는(independent) 부그래프를 'G의 요소'라고 한다.

연결요소(Connected Component) : 요소 내 모든 node쌍에 대해 경로가 존재하는 부그래프 S를 'G의 연결요소'라고 한다.


1. 전체 그래프에 대해 몇 번 DFS를 돌았는지 카운트한다.

    DFS의 시간복잡도는 O(V+E)이므로 전체 시간복잡도는 O(n+m)


2. Disjoint set이 몇 개인지 카운트한다.

   Union-Find 시간복잡도는 O(1), 초기화 O(n)

   카운트하는데 O(n)이므로 전체 시간복잡도는 O(n)

   *입력 O(m)인건 무시

'Problem Solving > 문제 풀이' 카테고리의 다른 글

10845 큐  (0) 2018.02.05
11651 좌표 정렬하기 2  (0) 2018.02.05
11724 연결 요소의 개수  (0) 2018.02.05
1520 내리막 길  (0) 2018.02.05
8595 히든 넘버  (0) 2017.06.13
10571 다이아몬드  (0) 2017.06.13
0 Comments
댓글쓰기 폼