On 02.07.2014 13:58, Borneq wrote:
> W dniu 2014-07-02 11:52, bartekltg pisze:
>>> Tych punktów jest na tyle mało, że czas kwadratowy nie za bardzo
>>> przeszkadza, ale w jaki sposób uzyskać czas liniowy?
>>
>> Bierzesz wierzchołek, wszystkich sąsiadów wyrzucasz. Bierzesz
>> pierwszy wolny wierzchołek, wyrzucasz wszystkich jego sąsiadów.
>> Powtarzasz do wyczerpania nieprzetworzonych wierzchołków.
>
> Jak biorę pierwszy wolny wierzchołek zamiast maksymalnego, to mi się nie
> udaje. Np. 0-1-2, wyrzucam 0, zostaje 1-2, muszę wyrzucić 1

I jest to zbiór niezależny maksymalny. Nikt nie obiecywał
największego;-)

Pewnie Twój średnio daje lepszy wynik, ale nie zawsze.
6
|
5
|
0-1-2-3-4
|
7
|
8

Tutaj Twój algorytm zwróci 4 elementy,
a da się 5.

pzdr
bartekltg