블로그 이사 중입니다 >> gumgood.github.io
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 |
- Tag
- DFS, disjoint set
0 Comments