11724 연결 요소의 개수

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