qkreltms   6년 전

"연결" 요소의 개수를 찾는 문제인데 

간선으로 연결이 되어있지 않은 컴포넌트도 결과 값에 포함된다는게 

지금와서 생각해보니 좀 이상하네요...

예를 들어

6 2

1 3

2 3

라는 값이 들어왔을 때 (1,2,3), (4), (5), (6) 총 4개가 나오는데

(1,2,3) 서로 간선으로 연결 됐기 때문에 답에 포함 되는게 이해가 되는데 

4, 5, 6은 답에 포함되는게 제목과 일치하지 않다는 생각입니다.

=========

위키피디아를 찾아보니 연결 요소 = 연결 그래프이고

연결 그래프 = 모든 두 꼭짓점 사이에 경로가 존재하는 그래프

방향이 없는 그래프 = 꼭지점 간에 구별이 없다.

즉, 방향 없는 그래프는 두 꼭짓점 사이에 경로가 없어도 연결 됐다고 인정된다??

제가 이해한게 맞을까요?

djm03178   6년 전

a에서 a로는 움직이지 않고 가만히 있어도 도달할 수 있기 때문에 아무런 간선을 거치지 않아도 됩니다. 즉, 간선을 0개 이용하는 "경로"인 것입니다.

댓글을 작성하려면 로그인해야 합니다.