다음 방향 그래프는 강력 연결 요소(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에서 다른 정점으로 갈 수 없다는 점에 어긋난다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 14년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기