ktoś mądry to sortowanie wymyślił 😀
generalnie to pewnie można zrobić tak, że dzielisz poksy na 2 zobry:
1. te wypuszczone
2. te zamknięte
i teraz wypuszczasz najpierw te spokojne
czyli przenosisz je do zbioru 1
teraz przeglądasz te elementy ze zbioru 1 i patrzysz jakby w drugą stronę
czyli jakie na nie poluja
zwiększasz licznik tamtym pokemonom o 1 i jak któryś będzie miał licznik >= 2 to go przenosisz do zbioru 1
itd
tylko trzeba uważać, żeby 2 razy nie przeglądnąć tej samej krawędzi, ale to można po prostu je usuwać i będzie git
i to jest złozność O(m) gdzie m to liczba krawędzi
tylko zastanawiam się, bo po przenoszeniu tych niebezpiecznych, ale które polują na bezpieczne, większa ilość niebezpiecznych będzie mogła przejść
czy to będzie w jakieś pętli while(true)?

no można  w while(true),
albo wrzucać do jakiejś kolejki krawędzie, które trzeba sprawdzić po wrzuceniu pokemona do grupy 1
musze sobie to rozrysować
na grafie bedzie to bardzo czytelne ;D

tak :d

genrealnie:
na kolejkę wrzucasz wierzchołki z grupy 1 i robisz while(!kolejka.empty())

i podczas obiegu kolejki czyli

while(!kolejka.empty()) {
wierzcholek w = kolejka.top(); kolejka.pop();

przeglądnij wszystkie krawędzie wchodzące do wierzchołka w,
jeśli krawędz chodzi z wierzchołka z grupy 2, zwiększ mu licznik, jeśli jego licznik jest == 2, wrzuć go na kolejkę

}

jesli wszystkie wierzchołki są w grupie 2 wygrałeś, jeśli nie to nie da się tego zrobić
okej, dzięki, musze to przemyśleć xD bo na grafach pierwszy raz coś robię

będziesz startował w cf dzisiaj? 😀
w sumie jeszcze się nie patrzyłem na tematy zadań, myśle że potem ogarnę, teraz te pokemony rysuję i próbuję zrozumieć twój pomysł 😀

bo musisz utworzyć drugą listę z krawędziami zwróconymi w drugą stronę, wiesz
a licznik na danym pokemonie to chodziło Ci "ilość pokemonów polujących na niego", czy "ilość pokemonów na które poluje"?
raczej to pierwsze, ale dla pewności pytam 😀

licznik zwiększasz tylko pokemonom w grupie 2 (czyli jeszcze nie wypuszczonym)
i chodzi o to, żeby na wolności były co najmniej 2 pokemony, na które dany pokemon poluje
bo te w grupie 1 to są te wypuszczone
i tylko te z licznikiem >= 2 wypuszczam

tak
i jeśli nie znajde takich a nadal będą w grupie 2 to nie da się

ale w praktyce to i tak będzie to przy wypuszczaniu licznik zawsze będzie równy 2, bo przegladając kolejke zwiększasz go o 1 i nie przeskakujesz itp
tak
okej, w miarę czaję ale jednak musze to calkiem rozrysowac i zobaczyc czy działa w praktyce xD
dzięki wielkie za pomoc

ok 😀
spx
mam jeszcze pytanie do jednego, wspomniałeś o złożoności o(m) przy liczeniu krawędzi przecinających dwa zbiory. Powiedzmy że mam już spokojne pokemony w grupie 1 i reszta w grupie 2. Żeby inkrementować liczniki tym z grupy 2 muszę iterować przez całą listę tyle razy ile jest pokemonów w grupie 1 (tzn za pierwszym razem szukam ile pokemonów poluje na pierwszego spokojnego i im inkrementuje, potem szukam ile pokemonów poluje na drugiego spokojnego itd.) Nie będzie to złożoność O(m*ilość_spokojnych_pokemonów)?
chyba że da się te liczniki załatwić podczas jednego przejazdu przez listę, ale nie za bardzo wiem jak

nie,
podczas przeglądania kolejki, przeglądasz każdą krawędź co najwyżej raz => złożność O(m)
no tak, ale przeglądając krawędzie mogą być takie, które mają jako "cel polowania" pokemona z tej grupy 2 i muszę chyba sprawdzić, czy ten cel polowania to jeden z spokojnych pokemonów

Na początki przeglądasz raz wszystkie pokemony i wrzucasz do gr 1 te które można od razu wypuścić
tak
i wszystkie krawędzie do kolejki?

Do kolejki wrzucasz wierzchołki nie krawędzie
Każdy wierzchołek zostanie wrzucony co najwyżej raz
Do kolejki
wierzchołki czyli pokemony z grupy 1?
te które przeszły właśnie?

Tak
chyba zaczynam rozumieć xD
po co ta kolejka była
o dobra czaję, tylko jeszcze nie za bardzo wiem jak zaimplementować grupę 2
bo z niej będę usuwać kolejne pokemony
i na końcu sprawdzać, czy ktokolwiek tam jest
to powinna być lista?

To znaczy możesz zrobić dodatkowa tablice booli
I jak przerzucasz pokemona to dajesz true
o rozmiarze n i oznaczać czy istnieje tam pokemon
okej
czaję, jeszcze raz dzięki wielkie 😀

Spoko 😀
A wiesz czemu zlozonosc O(m) lub raczej O(m+n)?
chwila
mówisz o złożoności całego algorytmu?

Tak
kurcze, na prawde nie wiem, wydaje mi sie ze to zależy od sytuacji, bo powiedzmy jak masz dużo elementów w kolejce i tak się składa że już żadnych nie da się przepuścić do grupy 1, to złożoność powinna być
o(m*bezpieczne_pokemony)
bo dla każdego elementu z kolejki sprawdza
a w kolejce teoretycznie może być n-1 elementów
też nie wiadomo ile będzie iteracji tego while(true) 😕
tzn while(kolejka.empty())
!kolejka.empty()*

Podczas przeglądania kolejki bierzesz pierwszy element i go popujesz z kolejki, później go już nie dodajesz,
Czyli do kolejki każdy element wejdzie co jawyzej raz, raz ja opuści,
Podczas tego jak zajmujesz się danym elementem z góry kolejki to przeglądasz wszystkie jego krawędzie, czyli przejrzysz w sumie wszystkie krawędzie bo z każdego elementu przejrzysz wszystkie wchodzące do niego

I to wychodzi O(n+m)
Jak się nie da już żadnych przepuścić to usuniesz wszystkie elementy z kolejki i tyle
I skończysz algorytm
okej, ale powiedzmy, że mam 5 elementów w kolejne, przeglądam pierwszy, szukam krawędzi (polujących na niego, w czasie O(m)), nie znajduję, nikomu licznika nie zwiększam, więc przechodzę do kolejnego elementu kolejki i znowu szukam krawędzi O(m)
i to już jest jakby 2*m, więc pesymistycznie nie powinno byc chyba O(m+n)

Ale to nie przeglądasz wszystkich krawędzi na raz
Tylko te które wchodzą do danego elementu
ale żeby sprawdzić które wchodzą to muszę przez całą listę przejść chyba

Ich jest jakieś a,
Do drugiego wchodzi b krawędzi
I jak zsumujess a+b+....+z to ci wyjdzie m czyli liczba krawędzi
Nie musisz przeglądać wszystkich
Możesz zrobić nowa listę, w której bedziesz miał dla danego elementu wszystkie te które do niego wchodzą
a no to tak, wtedy faktycznie
ja myślałem, że po tym chcesz jeździć

Nie
czyli w sumie najgorzej będzie n-1 dodatkowych list

No tak, ale liczba elementów w sumie w tych listach to będzie m
tak
w sumie możnaby na początku zrobić te n list i dla każdego pokemona
zapisywać kto na niego poluje

Tak, na podatku tworzysz ta listę
Listę list
to jest dobre i teraz rozumiem o co chodziło z usuwaniem krawędzi
żeby usuwać element z tej listy przy zwiększaniu licznika
tak?

To znaczy nie trzeba usuwać krawędzi
Bo i tak nie bedziesz później ich przeglądał jak już raz przeglądniesz
no racja
tylko max 1 raz moge przeglądać pokemona z grupy 1

Tak
To znaczy co to była grupa 1? 😀
Bo już sb zapomniałem
te które już są wypuszczone

No to tak
te listy list zawsze wydają mi się trochę meh pamięciowo
no ale bez tego złożoność będzie sporo większa

Będzie wtedy kwadratowa
No trochę to zajmuje, ale ciagle to jest linowa zlozonosc zajmowanego miejsca z duża stała
nom
spoko pomysł ;D
co prawda chyba tego sortowania na grafach nie użyłeś
chyba że ja tego nie widzę
no ale teraz jak zczaiłem te listy to wydaje sie bardzo logiczne to

To znaczy to jest prawie to samo co sortowanie topoligiczne, z ta różnica ze tu wrzucasz do kolejki element jak 2 sąsiadów jest już odwiedzonych a przy sortowaniu topo, wrzucasz dopiero jak wszyscy sąsiedzi będą przetworzeni, to znaczy jakby dopiero wtedy gdy byś wypuścił wszystkich pokemonow na kotorych poluje dany pokemon

A tu wystarczy ze są 2 wypuszczone
to jeszcze jedno 😀 czemu O(m+n) a nie O(m)
chodzi tylko o to, że alokujesz n list i tablice booli o rozmiarze n?
czy to "n" pojawia się jeszcze gdzieś indziej

Jeszcze podczas przeglądania kolejki, bo przeglądasz każdy element raz i jak np byś nie miał krawędzi w ogóle to i miał w kolejce wszystkie wierzchołki to i tak byś je przeglądnąć
a
no racja

Coś dzisiaj strasznie nie po polsku pisze 😀
ee nie spoko to wytłumaczyłeś
tylko ja powoli to trawię xD

Chodzi mi bardziej o moje błędy językowe 😀
a, to nie przeszkadzały ;D