ychooni   4년 전

(간선 수 = 정점 수 - 1) 을 만족하면 트리라고 해서 문제를 풀었는데요,


제가 뭘 간과하고 있는 걸까요? ㅜㅜ


yclock   4년 전

이 문제를 풀지 않았습니다. 소스를 자세히 읽지 않았습니다.


입력으로 주어지는 간선 (a, b)에서 a != b가 보장되지 않습니다.

(edge>>1) 부분에서 자기 자신이 사이클을 이루는 경우, 값이 내림으로 계산되어서 트리로 판단할 수 있을 것 같습니다.

edge == (vertex-1)<<1로 고쳐야 할 것 같습니다.

yclock   4년 전

길이가 1인 사이클을 고려하여 맞았습니다.

ychooni   4년 전

@yclock

답변 감사합니다. 

말씀하신것 처럼 a!=b라는 보장이 없고,  

a==b 인 경우 

(edge>>1) == vertex-1) 보다는 edge == (vertex-1)<<1 의 표현이 맞는 것 같습니다.

그런데, 위의 경우 또 제가 잘못한 것이,

테케가 여러개인데, 그래프 g를 초기화를 안해주어서 틀린게 일단 주된 문제였던 것 같구요.

음, 데이터가 약하다고 표현해야하나? . 

그래프 초기화만 추가하고 (edge>>1) == vertex-1) 코드를 그대로 사용했음에도 AC를 받았네요..


ps. 답변 뿐만아니라 님의 소스코드를 통해 많은 것 배워갑니다.(테케를 카운트 하는 변수를 이용해서 굳이 멤셋을 할 필요가 없다는 테크닉..ㅎ) 답변 감사합니다..!!

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