Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 79. (March 2013)

S. 79. We are given a weighted graph on N points and M edges with N\le 100\;000 and M\le 100\;000. For each edge e, decide whether there exists a minimal spanning tree containing e. A minimal spanning tree by definition is a spanning tree with the smallest total weight; a spanning tree is a tree that contains all the vertices of the graph together with some edges; and a tree is a graph without a (simple) cycle. A minimal spanning tree is said to contain e, if it is a minimal spanning tree with one edge being e.

Your program should read the values of N and M from the first line of the standard input, then the integers ki, vi and si (each separated by a space character) from the next M lines: ki and vi denote the endpoints of the ith edge with weight si. The ith line of the standard output should contain the word ``Igen'' (= yes), if there is a minimal spanning tree that contains the ith edge, and the word ``Nem'' (= no), if no such tree exists.

The table shows a sample input (``Példa bemenet'') together with the corresponding output (``Példa kimenet'').

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 1 second of running time. Partial points out of the 9 points can be obtained if your program can solve only smaller test cases within the allotted time, according to the following bounds:

\bullet 2 points for 0<M\le300;

\bullet 3 more points for 300< M\le 2\;000;

\bullet finally, 4 more points for the cases 2\;000< M\le
100\;000.

The source code (s79.pas, s79.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but with a short documentation (s79.txt, s79.pdf, ...) - also describing which developer environment to use for compiling - should be submitted in a compressed file s79.zip.

(10 pont)

Deadline expired on April 10, 2013.


Sorry, the solution is available only in Hungarian. Google translation

Megoldás

Lassú megoldás A Kruskal algoritmussal először besszük a kérdéses élet, majd utána a Kruskallal folytatjuk. Ezt minden élre külön külön eljátsszuk, ez azt jelenti, hogy mindne élre egy külön Kruskalt kell futtatnunk, viszont egyszerű, és nyilván jó megoldást ad.

Gyors, mlogn-es megoldás Azaz pont a Kruskal futásideje a megoldás futásideje is. Az az alapötlet, hogy a Kruskalt futtatjuk, csak épp nem a következő élről döntjük el, hogy bevesszük-e, hanem a következő kupac élről. Először pedig az összes élet kupacokba osztjuk, úgy, hogy egy kupacban az azonos súlyúak legyenek. Az általános lépésben a következő kupacot kell feldolgozni. ELőször minden élről eldöntjük, hogy be lehetne-e venni, azaz a két végpontja nem egy komponensben van-e. Ha be lehetne venni a feszítőfába, akkor kiírjuk. Ezután és csakis az egész kupac végignézése után újrakezdjük a végignézését a kupacnak, csak most valóban be is vesszük, ha nem okoz kört. Most már csak be kell bizonyítani, hogy ez így valóban megadja az összes olyan élet, ami szerepelhet egy minimális feszítőfában. Nyilván csak olyanokat adhat meg, ami szerepelhet, belátjuk, hogy az összes ilyet megadja: vegyünk egy s súlyú élet, és egy hozzá tartozó minimális feszítőfát. Ekkor az s-nél kisebb súlyú élek által alkotott összefüggőségi komponenseket a Kruskal során megkaptuk már. És akkor pont azt adja meg az algoritmus, hogy egy ilyen komponensben van-e ez az s súlyú él, vagy két komponens között vezet.

A Kruskal algoritmusról a Wikipedián lehet olvasni.

A mintamegoldás unióholvan adatszerkezettel (tehát gyorsan): main.cpp


Statistics:

6 students sent a solution.
10 points:Szabó 928 Attila, Vályi András.
2 points:2 students.
0 point:2 students.

Problems in Information Technology of KöMaL, March 2013