Trong một thí nghiệm giao phối giữa loài bọ, người ta đánh số chúng và cho chúng giao phối với nhau. Hãy kiểm tra xem có tồn tại con đồng tính trong những con được kiểm tra hay không?
Code Editor
Giải thích : Test 1: Có 3 con và tiến hành 3 thí nghiệm con 1 với con 2, nghĩa là nếu 1 là đực thì 2 là cái, 2 với con 3 vì con 2 là cái nên con 3 là đực. con 1 với con 3 cả 2 con là đực (đồng tính cmnr :D).
Giải thuật : Sử dụng DFS thay vì trước đây duyệt đồ thị chúng ta chỉ đánh dấu các vị trí đã đi qua là 1 thì giờ ta sẽ đánh dấu các cặp bọ bằng 2 giá trị là 1 và 2. 1 là con đực và 2 là con cái. Khi tồn tại 2 con đã đánh dấu cùng giá tri tức là nó đồng tính.
Giải thuật : Sử dụng DFS thay vì trước đây duyệt đồ thị chúng ta chỉ đánh dấu các vị trí đã đi qua là 1 thì giờ ta sẽ đánh dấu các cặp bọ bằng 2 giá trị là 1 và 2. 1 là con đực và 2 là con cái. Khi tồn tại 2 con đã đánh dấu cùng giá tri tức là nó đồng tính.
Solution