Hướng giải và viết chương trình C

ĐỀ : Quốc hội của một nước nọ có N nghị sĩ. Biết rằng mỗi nghị sĩ có không quá 3 kẻ thù tư tưởng trong quốc hội . Hãy giúp nước đó chia Quốc hội thành 2 viện sao cho trong mỗi viện, mỗi nghị sĩ có không quá một kẻ thù tư tưởng.

thuật toán : a chia quốc hội ra thành 2 viện A, B một cách bất kỳ. Với mỗi viện A, B, ta gọi s(A),
s(B) là tổng của tổng số các kẻ thù của mỗi thành viên tính trong viện đó. Giả sử rằng
cách chia này vẫn chưa thoả mãn yêu cầu, tức là vẫn có một nghị sĩ nào đó có nhiều hơn
1 kẻ thù trong viện của mình. Không mất tính tổng quát, giả sử nghị sĩ x thuộc A có ít
nhất 2 kẻ thù trong A. Khi đó ta thực hiện phép biến đổi sau: chuyển x từ A sang B để
được cách chia mới là A’ = A {x} và B’ = B ∪ {x}. Vì x có ít nhất 2 kẻ thù trong A và
A’ không còn chứa x nên ta có
s(A’) ≤ s(A) – 4 (trong tổng mất đi ít nhất 2 của s(x) và 2 của các kẻ thù của x
trong A)
Vì x có không quá 3 kẻ thù và có ít nhất 2 kẻ thù trong A nên x có nhiều nhất 1 kẻ thù
trong B (hay B’), cho nên
s(B’) ≤ s(B) + 2
Từ đó s(A’) + s(B’) ≤ s(A) + s(B) – 2. Như vậy nếu (A, B ) là một cách chia chưa thoả
mãn điều kiện thì ta có thể biến đổi A, B để có một cách chia mới có tổng s(A) + s(B)
nhỏ đi ít nhất 2 đơn vị. Rõ ràng quá trình này không thể thực hiện được mãi, có nghĩa là
tồn tại cách chia (A*, B*) mà ở đó không tồn tại nghị sĩ có quá 1 kẻ thù trong viện của
mình.

Giúp mình với. input ngoài đầu vào là n nghị sĩ có cần danh sách các nghị sĩ và liệt kê kẻ thù của mỗi nghị sĩ ko ? Hay sẽ có cách giải nào nữa ? HELPPPPP