Giải bóng đá
Xem dạng PDFMột giải thi đấu bóng đá gồm ~n~ đội thi đấu vòng tròn một lượt. Các đội bóng được đánh số thứ tự từ ~1~ đến ~n~. Theo thể lệ giải đấu, nếu trận đấu diễn ra với kết quả hòa, hai đội sẽ thi đấu luân lưu cho đến khi phân định thắng thua (nghĩa là các trận đấu đều được phân định thắng thua).
Hỏi có tồn tại một cách sắp xếp các đội theo thứ tự sao cho trong thứ tự đó, mỗi đội đều thắng trận đấu với đội liền sau mình? Trong trường hợp tồn tại, hãy xác định một cách sắp xếp như vậy.
Input
Dòng đầu tiên chứa số nguyên ~n~ ~(1 \leq n \leq 1000)~ --- số đội bóng tham dự giải đấu.
Dòng thứ ~i~ trong số ~n~ dòng tiếp theo chứa ~j~ kí tự '0' hoặc '1', kí tự thứ ~j~ thế hiện giá trị ~a_{ij}~:
- ~a_{ii}~ = 0 với mọi ~i~.
- ~a_{ij}~ = 1 nếu và chỉ nếu đội ~i~ thắng đội ~j~. Dữ liệu vào luôn thỏa mãn ~a_{ij}~ +~a_{ji}~ = 1 với ~i~ khác ~j~.
Chú ý: Có ~30\%~ số test có ~n \leq 9~.
Output
In ra ~-1~ nếu không tồn tại cách sắp xếp thỏa mãn yêu cầu. Trong trường hợp tồn tại, in ra ~n~ số nguyên là chỉ số của các đội bóng trong cách sắp xếp tìm được.
Sample Input
3
010
000
110
Sample Output
3 1 2
Bình luận
sắp xếp topo:))
đề không có trường hợp -1 đâu anh em để bị lừa
phải tự suy ra từ tính chất bạn ạ
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Ta có thể coi mỗi một đội là một nút, và mỗi trận đấu là một cạnh chỉ từ nút đội thua đến nút đội thắng đến nút đội thua. Bài toán của chúng ta được quy về việc chứng minh rằng một đồ thị gồm ~n~ đỉnh và ~n(n-1)/2~ cạnh luôn có một đường đi Hamilton.
Gọi ~P=~{~u1, u2, u3, ..., u(n-1), un~}~~ là đường đi đi qua nhiều đỉnh nhất trên đồ thị. Giả sử tồn tại một đỉnh ~u0~ thuộc đồ thị nhưng không thuộc ~P~.
Xét cạnh ~(u1, u0)~. Ta thấy được bắt buộc cạnh này phải đi từ ~u1~ đến ~u0~. Vì nếu cạnh đi từ ~u0~ đến ~u1~ thì sẽ mâu thuẫn với giả thiết ban đầu rằng ~P~ là đường đi qua nhiều đỉnh nhất trên đồ thị (|{~u0~} hợp ~P~|>|~P~|).
Tương tự, cạnh ~(un, u0)~ sẽ đi từ ~u0~ đến ~un~.
Vì ~u0~ sẽ nối với tất cả các đỉnh còn lại (đi vào hoặc đi ra), nên sẽ tồn tại ít nhất một giá trị ~i~ ~(1≤i<n)~ sao cho ~(ui, u0)~ đi từ ~ui~ đến ~u0~ và ~(u(i+1), u0)~ đi từ ~u0~ đến ~u(i+1)~. Đến đây, ta lại tìm thấy một đường đi đi qua nhiều đỉnh hơn ~P~ ~(u1→u2→...→ui→u0→u(i+1)→...→u(n-1)→un)~.
Do đó, đường đi đi qua nhiều đỉnh nhất của đồ thị như đề bài sẽ luôn là đường đi Hamilton. Mà vì ta luôn tìm được đường đi đi qua nhiều đỉnh nhất của một đồ thị có hướng nên sẽ luôn tìm được đường đi Hamilton.