B. Сүлжээний топологи

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Энэ бодлогод сүлжээний топологи загварын хялбаршуулсан хэлбэрийг ашиглана, нөхцөлийг анхааралтай уншаад шийдэл хөгжүүлэхдээ баримталж ажиллана уу.

Поликарпус том корпорацид системийн админаар үргэлжлүүлэн ажиллаж байна. Энэ корпорацийн компьютерийн сүлжээ $n$ компьютерээс тогтох ба эдгээрийн зарим нь каблиар холбогдсон. Компьютерууд $1$-c $n$ хүртэл бүхэл тоогоор дугаарлагдсан. Ямар ч хоёр компьютер хоорондоо шууд каблиар эсвэл бусад компюьтеруудаар дамжин холбогдсон байна.

Поликарпус сүлжээний топологийг олж мэдэхээр шийдсэн. Сүлжээний тополог нь сүлжээний төхөөрөмжүүдийн холболтууд болон байрлалыг харуулдаг схем буюу сүлжээний тохиргоог тодорхойлох зүйл юм.

Поликарпус гурван үндсэн сүлжээний тополог буюу шугаман, цагираг, од топологуудыг мэднэ. Шугаман тополог нь бүх компьютер холбогдсон дундын каблиар илэрхийлэгдэнэ. Цагираг топологт кабль компьютер бүрийг яг хоёр компьютертэй холбодог. Од топологийн хувьд сүлжээний бүх компьютер төв зангилаатай холбогдоно.

Эдгээр сүлжээний топологи бүрийг холбогдсон чиглэлгүй графаар дүрслэе. Шугаман тополог нь замын эхний болон төгсгөлийн хоёр зангилаанаас бусад зангилаа бүр бусад хоёр зангилаатай холбогдсон байх зам бүхий холбогдсон граф байна. Цагираг тополог нь бүх зангилаа нь өөр хоёр зангилаатай холбогдсон байх холбогдсон граф байна. Од тополог нь төв зангилаа нь тусгаарлах ба бусад бүх зангилаатайгаа холбогдсон байх холбогдсон граф байна. Тодорхой болгохын тулд зургийг харна уу.

(1) -- шугаман, (2) -- цагираг, (3) -- од

Танд Поликарпусын корпорацийн компьютерийн сүлжээг тодорхойлох холбогдсон чиглэлгүй граф өгөгдсөн. Түүнд өгөгдсөн сүлжээ нь ямар топологийнх вэ гэдгийг олоход нь туслана уу. Хэрвээ боломжгүй бол сүлжээний топологийг үл мэдэгдэх тополог гэж нэрлэнэ үү.

Оролт

Эхний мөрөнд зайгаар тусгаарласан хоёр бүхэл тоо $n$ ба $m$ $(4 ≤ n ≤ 10^{5}; 3 ≤ m ≤ 10^{5})$ байх ба харгалзан граф дахь зангилаа болон ирмэгүүдийн тоо юм. Дараагийн $m$ мөрөнд графийн ирмэгүүдийн тайлбар байна. $i$-р мөрөнд зайгаар тусгаарласан хоёр бүхэл тоо $x_{i}$, $y_{i}$ $(1 ≤ x_{i}, y_{i} ≤ n)$ байх буюу $i$-р ирмэгээр холбогдсон зангилаануудын дугаар юм.

Өгөгдсөн граф нь холбогдсон байна. ямар ч хоёр зангилааны хооронд хамгийн ихдээ нэг л ирмэг байна. Ямар ч ирмэг зангилааг өөртэй нь холбохгүй.

Гаралт

Өгөгдсөн графийн топологийн нэрийг нэг мөрөнд хэвлэ. Хэрвээ хариулт шугаман топологи байвал "$bus topology$" (хашилтгүйгээр) гэж хэвлэ, хэрвээ хариулт цагираг байвал "$ring topology$" (хашилтгүйгээр) гэж хэвлэ, харин од байвайл "$star topology$" (хашилтгүйгээр) гэж хэвлэ. Хэрвээ дээрх хариултуудад таарахгүй байвал "$unknown topology$" (хашилтгүйгээр) гэж хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
4 3
1 2
2 3
3 4
Гаралт
bus topology
Оролт
4 4
1 2
2 3
3 4
4 1
Гаралт
ring topology
Оролт
4 3
1 2
1 3
1 4
Гаралт
star topology
Оролт
4 4
1 2
2 3
3 1
1 4
Гаралт
unknown topology
Сэтгэгдлүүдийг ачааллаж байна...