djm03178   2년 전

  1. ***********************테스트 케이스마다 초기화를 잘 하세요.*********************** 간선 정보, 정답 여부, 큐 등등 매 케이스마다 새롭게 시작해야 하는 건 반드시 그 루프의 시작에서 초기화합시다. 테스트 해볼 때도 1개씩만 하지 말고, 다수의 케이스를 연속으로 넣어서 항상 잘 나오는지 확인하세요. 그리고 매 케이스마다 개행 문자를 반드시 출력하세요. 그리고 Yes, yes 가 아니라 YES입니다.
  2. 1번 정점에서만 탐색을 해서는 안 됩니다. 1번 정점과 연결되지 않은 다른 정점들 사이에서 이분 그래프를 못 만들 수 있습니다. 1번 뿐만 아니라, 어느 정점이라도 마찬가지입니다. 주어지는 그래프는 연결 그래프가 아닐 수 있습니다.
  3. 간선 정보 순서대로, 또는 임의의 순서로 정렬해놓고 하나씩 보면서 집합을 임의로 정해주는 것도 안 됩니다. 지금 당장 집합을 정한 것 때문에 나중에 이분 그래프를 못 만들게 될 수도 있습니다. 그래프 정보가 완전히 들어오기 전까지는 섣부른 판단은 금물입니다.
  4. 한 정점에서 탐색을 시작했더니 답이 NO로 판명났으면, 그 답을 다시 YES로 바꿀 일은 절대로 없습니다. 예를 들어 1번 정점에서 탐색했더니 이분 그래프를 못 만들었다면, 4번 정점에서 탐색했더니 만들 수 있었다고 해도 답이 YES가 되지는 않습니다.

niklasjang   2년 전

  1. 1번 정점에서만 탐색을 해서는 안 됩니다. 1번 정점과 연결되지 않은 다른 정점들 사이에서 이분 그래프를 못 만들 수 있습니다.

이 부분이 이해가 안됩니다.

1번 정점과 연결되지 않은 정점이라고 한다면, unconnected Node가 있으면서 이분 그래프를 만족하는 경우가 있다는 말씀이신가요?

niklasjang   2년 전

A  ---간선---   B 

G  ---간선---  D

C  ---간선---   E

이렇게 생긴 하나의 그래프도 이분 그래프인가요?

djm03178   2년 전

1번과 2번 정점이 있고, 둘이 연결되지 않았다면 이분 그래프입니다. 둘을 서로 다른 집합에 넣으면, "그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때" 에서 어기는 부분이 없습니다. 둘이 서로 다른 집합이고, 인접하지 않죠.

djm03178   2년 전

네, 저것도 이분 그래프입니다. 예를 들면, AGC가 한 집합이고, BDE가 한 집합이면 AGC 사이에서 서로를 잇는 간선이 없고, 마찬가지로 BDE 사이에서 서로를 잇는 간선도 없으니까 이분 그래프입니다.

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