Az S. 136. feladat (2019. szeptember)

S. 136. Adott egy \(\displaystyle N\) csúcsú, \(\displaystyle M\) élű egyszerű gráf (nincs többszörös él vagy hurokél, de nem feltétlenül összefüggő). A csúcsokat 0-tól \(\displaystyle (N-1)\)-ig indexeljük. A gráf összes csúcsa fekete vagy fehér. Jelölje \(\displaystyle f(x)\) az \(\displaystyle X\) csúcs színét. Cseresznyének hívunk egy \(\displaystyle (A,B,C)\) rendezett csúcshármast, ha páronként különbözőek és létezik az \(\displaystyle A-B\), valamint a \(\displaystyle B-C\) csúcspárok közt él. Egy \(\displaystyle (A,B,C)\) cseresznye finom, ha \(\displaystyle f(A)=f(C)\) és \(\displaystyle f(A)\ne f(B)\). Adjuk meg, hogy egy él behúzásával legföljebb mennyire növelhető a finom cseresznyék száma. (\(\displaystyle A\) és \(\displaystyle B\) csúcs összeköthető egy éllel, ha \(\displaystyle A\ne B\), és eddig nem létezett köztük él.)

Standard bemenet: az első sor tartalmazza \(\displaystyle N\)-et és \(\displaystyle M\)-et. A következő sor \(\displaystyle N\) darab számot tartalmaz: az \(\displaystyle i\)-edik szám az \(\displaystyle i-1\) indexű csúcs színét határozza meg, 0 ha fekete, 1 ha fehér. A következő \(\displaystyle M\) sor mindegyike két számot tartalmaz. Az \(\displaystyle i\)-edik sor az \(\displaystyle i\)-edik él két végpontjának csúcsindexét adja meg.

Standard kimenet: a maximálisan elérhető finom cseresznyék száma.

Korlátok: \(\displaystyle 3\le N\le {10}^{5}\), \(\displaystyle 0\le M\le \min (10^{5},N^{2}-N-1)\). Időkorlát: 0,3 mp.

Értékelés: A pontok 50%-a kapható, ha a gráf fa.

Példa:

(10 pont)

A beküldési határidő 2019. október 10-én LEJÁRT.

Statisztika:

14 dolgozat érkezett.
10 pontot kapott:	Németh Márton, Noszály Áron, Szente Péter, Varga 256 Péter.
7 pontot kapott:	2 versenyző.
6 pontot kapott:	3 versenyző.
4 pontot kapott:	2 versenyző.
2 pontot kapott:	1 versenyző.
1 pontot kapott:	2 versenyző.

A KöMaL 2019. szeptemberi informatika feladatai