Feladat

Adott egy N csúcsú gráf, ahol legfeljebb 5 kivétellel minden csúcs foka legfeljebb 2. Adjuk meg a maximális független csúcshalmaz méretét. Avagy mesével: N ember közül – legfeljebb 5 kivétellel – mindenki legfeljebb 2 másikat ismer. Legfeljebb hány ember tudunk kiválasztani, hogy közülük senki ne ismerjen senkit?

input

Az első sor tartalmazza a csúcsok N, és az élek M számát, ahol 2<=N<=10 000, 0<=M<=100 000. A következő M sor mindegyikében két szám található, az adott él két végpontja. (Irányítatlan gráf.)

output

Kiírni egyetlen számot, a maximális független csúcshalmaz elemszámát kell.

Olimpiai válogatóverseny, 2013/3

A bejegyzés trackback címe:

Kommentek:

A hozzászólások a vonatkozó jogszabályok  értelmében felhasználói tartalomnak minősülnek, értük a szolgáltatás technikai  üzemeltetője semmilyen felelősséget nem vállal, azokat nem ellenőrzi. Kifogás esetén forduljon a blog szerkesztőjéhez. Részletek a  Felhasználási feltételekben és az adatvédelmi tájékoztatóban.