jjh4698   9달 전

이분그래프를  dfs로 구현을 해봤는데요

먼저 루트노드 1을 기준으로       인접리스트로 입력을 받았습니다.


예제에 나와있는데로 입력받으면

1    2

2    3

3   4

4   2                     이렇게 단방향으로만 인접리스트 벡터에 넣어주고 


dfs를 돌리면

1인 루트노드는 색깔 1을 기준으로 자신과 연결된 정점을 3-1 의 색깔로 칠하면서 재귀하게 하였습니다.

그리고 최종적으로 모든 노드를 방문했다고 가정했을때,   각 행 과 연결된 열 노드들의 색깔이 같은것이 있다면

이것은 이분그래프가 아니고, 없다면 이분그래프로 판별하게 하였습니다.


근데  위에서 처럼 단방향으로 제출을했을때는 틀렸습니다가 나오고 

양방향으로 넣어줬을때   v[x].push_back(y); v[y].push_back(x) 는 맞았습니다가 나오는 이유가 무엇일까요?? 


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