11724번 - 연결 요소의 개수
"연결" 요소의 개수를 찾는 문제인데
간선으로 연결이 되어있지 않은 컴포넌트도 결과 값에 포함된다는게
지금와서 생각해보니 좀 이상하네요...
예를 들어
6 2
1 3
2 3
라는 값이 들어왔을 때 (1,2,3), (4), (5), (6) 총 4개가 나오는데
(1,2,3) 서로 간선으로 연결 됐기 때문에 답에 포함 되는게 이해가 되는데
4, 5, 6은 답에 포함되는게 제목과 일치하지 않다는 생각입니다.
=========
위키피디아를 찾아보니 연결 요소 = 연결 그래프이고
연결 그래프 = 모든 두 꼭짓점 사이에 경로가 존재하는 그래프
방향이 없는 그래프 = 꼭지점 간에 구별이 없다.
즉, 방향 없는 그래프는 두 꼭짓점 사이에 경로가 없어도 연결 됐다고 인정된다??
제가 이해한게 맞을까요?
a에서 a로는 움직이지 않고 가만히 있어도 도달할 수 있기 때문에 아무런 간선을 거치지 않아도 됩니다. 즉, 간선을 0개 이용하는 "경로"인 것입니다.
댓글을 작성하려면 로그인해야 합니다.
qkreltms 6년 전 1
"연결" 요소의 개수를 찾는 문제인데
간선으로 연결이 되어있지 않은 컴포넌트도 결과 값에 포함된다는게
지금와서 생각해보니 좀 이상하네요...
예를 들어
6 2
1 3
2 3
라는 값이 들어왔을 때 (1,2,3), (4), (5), (6) 총 4개가 나오는데
(1,2,3) 서로 간선으로 연결 됐기 때문에 답에 포함 되는게 이해가 되는데
4, 5, 6은 답에 포함되는게 제목과 일치하지 않다는 생각입니다.
=========
위키피디아를 찾아보니 연결 요소 = 연결 그래프이고
연결 그래프 = 모든 두 꼭짓점 사이에 경로가 존재하는 그래프
방향이 없는 그래프 = 꼭지점 간에 구별이 없다.
즉, 방향 없는 그래프는 두 꼭짓점 사이에 경로가 없어도 연결 됐다고 인정된다??
제가 이해한게 맞을까요?