Module: Cari secara mendalam. DFS


Problem

5 /12


graf dwipartit

Theory Click to read/hide

Graf dwipartit
 
Graf dwipartit - graf yang bucunya boleh dibahagikan kepada dua set supaya setiap tepi menghubungkan bucu daripada set berbeza.


Selalunya dalam konteks graf dwipartit, konsep warna bucu digunakan. Membahagikan graf kepada dua bahagian dipanggil mewarna bucunya dengan dua warna berbeza. Setiap tepi mesti menyambungkan bucu dengan warna yang berbeza.

DFS. 
 

Algoritma

Kami mula melukis dari bucu arbitrari, yang kita lukis dalam warna arbitrari.
Apabila melepasi setiap tepi, cat bucu seterusnya dalam warna bertentangan.
Jika, semasa melelaran di atas bucu jiran, kita menjumpai bucu yang sudah dicat dalam warna yang sama dengan warna semasa, maka terdapat kitaran ganjil dalam graf, yang bermaksud ia bukan dwipartit.

Problem

Sesuatu graf dipanggil bipartit jika bucunya boleh diwarnakan dalam dua warna supaya tiada tepi yang menghubungkan bucu dengan warna yang sama (iaitu, setiap tepi pergi dari bucu warna pertama ke bucu ke-2) .
Diberi graf. Ia dikehendaki menyemak sama ada ia adalah dwipartit, dan jika ya, warnakan bucunya.
 
Input
Baris pertama pertama mengandungi nombor N - bilangan bucu graf (tidak melebihi 100). Seterusnya datang matriks bersebelahan - matriks NxN 0 dan 1 (0 bermaksud tiada tepi, 1 bermaksud kehadiran). Graf tidak terarah, tanpa gelung.
 
Imprint 
Pada baris pertama cetak salah satu mesej YA atau NO (bergantung pada sama ada graf adalah dwipartit atau tidak). Jika jawapannya ialah YA, dalam baris kedua cetak nombor N - warna untuk mewarnakan bucu: untuk warna pertama gunakan nilai 1, untuk warna kedua - nilai 2. Bucu pertama hendaklah warna 1.
 
Contoh

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Input Output
1
3
0 1 1
1 0 1
1 1 0
 TIDAK
2
3
0 1 1
1 0 0
1 0 0
YA
1 2 2