PTIT121G spoj PTIT – Quan hệ

Chúng tôi nhận thiết kế web công ty, thiết kế web thương mại điện tử, shop, thiết kế web blog cá nhân, viết phần mềm PC.

Liên hệ ngay: 035.870.8844 - Giá chỉ từ 2-3 triệu.

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 *