ПЕТИ МЕЖДУУНИВЕРСИТЕТСКИ ТУРНИР ПО ПРОГРАМИРАНЕ

БСУ, Бургас, 19 май 2002 г.

Задача F.

 АВТОБУСНИ ЛИНИИ

В един град има изградена мрежа от автобусни линии. Те са номерирани с последователни цели положителни числа, започвайки от 1, като най-големият номер не надминава 1000. Всяка линия има определен брой спирки (най-много 1000). Спирките имат отделна номерация за всяка линия. Номерата им са последователни цели числа по маршрута на автобуса и започват с 1. Началната и

 крайната спирки са различни и по маршрута няма повтарящи се спирки. Някои от тези спирки са общи за повече от една автобусна линия. Една такава спирка може да имат различни номера спрямо различните автобусни линии. Всички линии са двупосочни. Мрежата е такава, че ако две спирки се свързват чрез повече от една линия, тези линии минават по различни улици.

Кметът на града решил да оптимизира броя на линиите, като ги сведе до възможния минимум, но така че пътниците пак да могат да пътуват между всеки две спирки, между които дотогава това е било възможно, като се използва евентуално и прекачване. Освен това, трябва да е възможно, пътувайки по новите линии, пътниците, ако желаят да могат да минават през всичките улици, по които е могло да се пътува и преди реформата. Напишете програма

LINES.EXE, която намира търсения минимален брой линии. При новите линии се допуска началната и крайната спирки да съвпадат, разрешено е маршрутът да прави примки, т.е. някои от спирките да се повтарят, но не е разрешено автобусната линия да минава повече от веднъж по една и съща улица между две съседни спирки.

Входната информация се чете от текстов файл

LINES.INP, който съдържа данни за няколко изградени мрежи от автобусни линни. Данните за всяка мрежа започват с ред във файла, в който е записано едно цяло число, равно на броя на линиите. Следва ред, в който, разделени с по една шпация са записани бройките на спирките на автобусните линии, подредени по нарастване на номерата на линиите. В тези бройки са включени и крайните спирки. Следват толкова на брой групи от редове, колкото са линиите. В тези групи се описват линиите в растящ ред на техните номера. Всяка от тези групи започва с ред, в който е записан номерът на линията. Останалите редове в групата са толкова на брой, колкото са спирките и всеки от тези редове описва по една спирка според растящия ред на номерата на спирките. Редът съдържа няколко двойки цели числа и започва с още едно число, равно на броя на тези двойки. Всяка двойка е съставена от номер k на друга автобусна линия, която спира на съответната спирка и поредния номер на тази спирка по маршрута на линия номер k. Ако на някоя от спирките не спират автобуси от други линии, на съответния ред във файла е записано числото 0. За разделител между числата в редовете на файла навсякъде се използва по една шпация. Появата на нула във файла, там където се очаква брой на линиите за поредната мрежа от линии, означава край на входната информация.

Изходната информация трябва да бъде записана в текстовия файл

LINES.OUT, по едно число на ред, което да е равно на намерения минимален брой автобусни линии, съответно за всяка от мрежите във входния файл.

Пример:

LINES.INP LINES.OUT

2 1

2 2 1

1

0

1 2 2

2

0

1 1 2

3

2 2 2

1

2 2 1 3 1

2 2 2 3 2

2

2 1 1 3 1

2 1 2 3 2

3

2 1 1 2 1

2 1 2 2 2

0