Dopelnienie grafu, jak policzyc powstale grafy

0

Nigdzie nie moge znalezc odpowiedzi na pytanie jak policzyc grafy powstale w wyniku utworzenia dopelnienia grafu.

Mam liste sasiedztwa wierzcholkow (lub jesli to moze ulatwic to bardzo latwo moge uzyskac spis wszystkich krawedzi).

Przykladowa lista sasiedztwa:
1: 2,4
2: 3,5
3: 4,5
4: 5

Graf jest nieskierowany, dlatego jesli 5 jest sasiadem 4 to i 4 jest sasiadem 5.

Dopelnienie grafu powinno wygladac tak:
1: 3,5
2: 4

Sasiadujace wierzcholki tworza krawedzie, ktorych nie bylo w pierwotnym grafie. Powstaly dwa grafy.

Mozna to zaimpementowac tak ze dla kazdego wierzcholka po kolei bede sprawdzal czy jest sasiadem kolejnych wierzcholkow. Jesli nie to do kolejki dorzuce ten nie sasiadujacy wierzcholek. Byloby to jakby przejscie po nowo powstalym grafie. Gdy skoncza sie wierzcholki, mozna wziąć kolejny nie odwiedzony i zrobic to samo, w miedzyczasie podliczajac ze przechodzi sie juz po kolejnym powstalym grafie. Jednak takie rozwiazanie ma zlozonosc kwadratowa. Jest na to jakis prostrzy sposob?

0

Wsytarczy wypełnić macież sąsiedztw. Pozostałe puste miejsca są dopełnieniem.

0

1) Macierz macierzą, ale tutaj chodzi o macierz 100000 x 100000 ;>
2) To zadanie z Olimpiady informatycznej. W oi chodzi o samodzielne rozwiązywanie zadań...

0
spływaj napisał(a)

1) Macierz macierzą, ale tutaj chodzi o macierz 100000 x 100000 ;>
2) To zadanie z Olimpiady informatycznej. W oi chodzi o samodzielne rozwiązywanie zadań...

Masz racje, ze chodzi o zadanie z OI. Rzeczywiscie moze o zbyt wiele spytalem. :)

Macierz jest dobra dla malych liczb, ale w tym wypadku zajmowalaby duzo za duzo. ;) Jest na to inny sposob, choc ten ktory wymyslilem jest nieco wadliwy.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0