PTIT121G spoj PTIT – Quan hệ

Nguồn đề bài: http://www.spoj.com/PTIT/problems/PTIT121G/

1. Đề bài PTIT121G spoj

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 (quy ước A[i,i]=0). 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?

Input

Gồm nhiều bộ test, mỗi bộ test có dạng như sau:

–          Dòng thứ nhất: Ghi số nguyên dương 1<=N <= 100

–          N dòng tiếp theo, dòng thứ i ghi N số A[i][1], …, A[i][N].

Bộ test kết thúc bởi dòng chứa số N=0.

Output

Với mỗi bộ test, in ra trên một dòng:

–          ‘YES’ nếu có thể chia.

–          ‘NO’ nếu không thể chia.

Example

INPUTOUTPUT
11

0 1 0 0 1 1 0 0 0 0 0

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 1 0 0 1

0 0 0 0 0 0 0 0 0 1 0

0

YES

2. Hướng dẫn PTIT121G spoj PTIT – Quan hệ

Xây dựng mảng DD[1..N] như sau:

  • Khởi tạo mọi giá trị bằng 0.
  • Bắt đầu chia nhóm từ người thứ nhất cho tới người thứ N. Khi xét người thứ i, những khả năng sau có thể xảy ra:

+ Nếu DD[i] = 0 (chưa được xếp nhóm) thì xếp vào nhóm 1(DD[i] = 1) và xếp những người j quen i vào nhóm 2 (cho DD[j] =2).

+ Nếu DD[i] =  1 và trong số những người quen i có một người j mà DD[j] cũng bằng 1 thì kết luận không xếp được.

+Nếu DD[i] = 2 và trong số những người quen i có một người j mà DD[j] cũng bằng 2 thì kết luận không xếp được.

3. Code tham khảo PTIT121G spoj PTIT – Quan hệ

One thought on “PTIT121G spoj PTIT – Quan hệ

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *