Bài 2: Quan hệ Cĩ N người mang tên tương ứng là 1, 2, ..., N và tình trạng quen biết của N người này được cho bởi mảng
đối xứng A[1..N,1..N] trong đĩ A[i,j] = A[j,i] = 1 nếu i quen j và bằng 0 nếu i khơng quen j. Hãy xét xem liệu cĩ thể chia N
người đĩ thành 2 nhĩm mà trong mỗi nhĩm hai người bất kì đều khơng quen nhau?
Dữ liệu vào được cho bởi file QHE.INP trong đĩ dịng thứ nhất ghi số nguyên dương N <= 100, trong N dịng tiếp
theo, dịng thứ i ghi N số A[i,1], ..., A[i,N].
Kết quả ghi ra file QHE.OUT như sau:
oNếu khơng cĩ thể , ghi -1
oNếu cĩ thể, ghi ra hai dịng, dịng thứ nhất tên những người thuộc nhĩm 1, dịng thứ hai tên những người thuộc
nhĩm 2.
Ví dụ:
QHE.INP QHE.OUT
11
1 3 4 7 8 11
0 1 0 0 1 1 0 0 0 0 0
2 5 6 9 10
1 0 1 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 0 0 1 0 0
1 0 0 1 0 0 0 0 0 0 0
1 0 0 1 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0 0 1 0
0 0 0 0 0 0 0 0 1 1 0
0 0 0 1 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 1 0
Bạn đang xem bài 2: - DE THI HSG TIN 11 CO DAP AN