Module: Derinlemesine arayın. DFS


Problem

5 /12


ikili grafik

Theory Click to read/hide

İkili grafik
 
İki parçalı grafik - köşeleri iki kümeye bölünebilen bir grafik, böylece her bir kenar birbirine bağlanır. farklı kümelerden köşeler.


Genellikle ikili grafikler bağlamında, renkler köşeler kavramı kullanılır. Bir grafiği iki parçaya bölmeye köşelerini iki farklı renkle renklendirme denir. Her kenar, farklı renkteki köşeleri birleştirmelidir.

DFS. 
 

Algoritma

Boyayı isteğe bağlı bir renge boyadığımız isteğe bağlı bir tepe noktasından başlatıyoruz.
Her kenar boyunca geçerken, bir sonraki köşeyi zıt renge boyayın.
Komşu köşeler üzerinde yineleme yaparken, halihazırda geçerli olanla aynı renge boyanmış bir tepe noktası bulursak grafikte tek döngü vardır, bu da bunun iki parçalı olmadığı anlamına gelir.

Problem

Bir grafiğin köşeleri, aynı renkteki köşeleri birleştiren kenarlar olmayacak şekilde iki renkte boyanabiliyorsa (yani, her kenar 1. rengin tepesinden 2. rengin tepe noktasına gidiyorsa) iki parçalı olarak adlandırılır. .
Verilen bir grafik. Çift parçalı olup olmadığı kontrol edilmeli, öyleyse köşeleri renklendirilmelidir.
 
Giriş
İlk satır ilk olarak N sayısını içerir - grafik köşelerinin sayısı (100'ü geçmez). Ardından bitişiklik matrisi gelir - 0 ve 1'den oluşan bir NxN matrisi (0, kenar yok, 1 varlık anlamına gelir). Grafik yönsüzdür, döngüler yoktur.
 
Künye 
İlk satıra EVET  veya HAYIR mesajlarından birini yazdırın (grafiğin ikili olup olmamasına bağlı olarak). Yanıt EVET ise, ikinci satıra N sayıları yazdırın - köşeleri renklendirecek renkler: ilk renk için 1 değerini kullanın; ikinci renk - 2 değeri. İlk köşe, renk 1 olmalıdır.
 
Örnekler

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!

# Girdi Çıktı
1
3
0 1 1
1 0 1
1 1 0
 HAYIR
2
3
0 1 1
1 0 0
1 0 0
EVET
1 2 2