다음 방향 그래프는 강력 연결 요소(strongly connected … | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
다음 방향 그래프는 강력 연결 요소(strongly connected component)들이 존재한다. 각 강력 연결 요소에 있는 정점들의 개수를 구한 후, 큰 수부터 나열한 것은?
1
4, 1, 1
2
4, 2
3
5, 1
4
6
해설
강력 연결 요소는 {a, c, d, e, f}와 {b} 두 개이므로 정점 수는 5, 1이다.
a→d→c→f→a 와 a→d→e→f→a 의 두 순환이 정점 a, c, d, e, f를 서로 오갈 수 있게 묶는다. 반면 b는 들어오는 간선만 있고 나가는 간선이 없어 홀로 하나의 요소가 된다.
- 4, 1, 1이나 4, 2로 나누는 것은 c 또는 e가 순환에 포함된다는 점을 놓친 것이다.
- 6개 전체가 하나라고 보는 것은 b에서 다른 정점으로 갈 수 없다는 점에 어긋난다.
오류나 개정된 내용이 보이면 알려주세요
