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

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ệ

const   fi='';
        fo='';
        nmax=100+1;
type    data=longint;
var
        f,f1:text;
        n:data;
        A:array[1..nmax,1..nmax] of byte;
        DD:array[1..nmax] of byte;

procedure xuli;
var     i,j,k,tmp:data;
begin
        fillchar(dd,sizeof(dd),0);
        for i:=1 to n-1 do
                for j:=i+1 to n do
                        if a[i,j]=1 then
                                begin
                                        if (dd[i]=0) and (dd[j]=0) then
                                                begin
                                                        dd[i]:=1;
                                                        dd[j]:=2;
                                                        continue;
                                                end;

                                        if dd[i]<>0 then
                                             begin
                                                if dd[i]=1 then
                                                        tmp:=2
                                                else
                                                        tmp:=1;

                                                if dd[j]=0 then
                                                        begin
                                                                dd[j]:=tmp;
                                                        end
                                                else
                                                        if dd[j]=dd[i] then
                                                                begin
                                                                        writeln(f,'NO');
                                                                        exit;
                                                                end;
                                             end
                                        else
                                                begin
                                                        if dd[j]=1 then
                                                                tmp:=2
                                                        else
                                                                tmp:=1;
                                                        dd[i]:=tmp
                                                end;
                                end;
               writeln(f,'YES');
end;


procedure docfile;
var     i,j,tmp:data;
begin
        assign(f1,fi); reset(f1);
        assign(f,fo); rewrite(f);
        readln(f1,tmp);
        repeat
        if tmp=0 then break;
        n:=tmp;
        for i:=1 to n do
                begin
                        for j:=1 to n do
                                read(f1,a[i,j]);
                        readln(f1);
                end;
        xuli;
        readln(f1,tmp);
        until tmp=0;
        close(f1);
        close(f);
end;

begin
        docfile;
end.