e-olymp
Məsələlər

Maksimal dəst

Maksimal dəst

Verilmiş G(V, E) qrafı üçün elə g(v, e) alt qrafı dəst adlanır ki, v-yə daxil olan bütün v1, v2 təpə nöqtələri cütlüyü üçün e-yə daxil olan (v1, v2) tilləri mövcud olsun. Maksimal dəst elə dəstdir ki, maksimal sayda təpə nöqtələri olsun.

Giriş verilənləri

Giriş verilənləri bir neçə testi ehtiva edir. Hər bir test aşağıdakıları ehtiva edir:

  • Testin birinci sətrində qrafın təpə nöqtələrinin sayı n (1 < n50) verilir.
  • Növbəti n sətrin hər biri (i (sətir nömrəsi) və j (sütun nömrəsi) təpə nöqtələrinin arasında tilin olmasını və ya olmamasını göstərən) 0 və ya 1-lərdən ibarət olan n sayda ədədi ehtiva edir.

n = 0 ilə başlayan test giriş verilənlərinin sonuna işarə edir. Bu testi emal etmək lazım deyil.

Çıxış verilənləri

Hər bir test halı üçün ayrı-ayrı sətirdə yeganə ədədi – qrafdakı maksimal dəstin təpə nöqtələrinin sayını verin.

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB
Giriş verilənləri #1
5
0 1 1 0 1
1 0 1 1 1
1 1 0 1 1
0 1 1 0 1
1 1 1 1 0
0
Çıxış verilənləri #1
4