Zadanie Skarbonki OI, Silnie Spójne Składowe, Optymalizacja Pamięci

Question

Mam takie zadanie: https://szkopul.edu.pl/problemset/problem/lm7lS3cC3aTRwlRaCztGRkov/site/?key=statement

Rozwiązanie jest dobre, a mianowicie: traktuję całość jako graf o n wierzchołkach i n krawędziach, a mianowicie, jeśli wiemy, że numer i-ty klucz jest w skarbonce x, to robimy krawędź skierowana i - > x, i taki graf dzielimy na silnie spójne składowe, i wyn to ile wszystkich spójnych składowych - ile_krawedzi w grafie, gdzie każda spójna składowa to wierzchołek. Tylko jest jeden problem, a mianowicie pamięc. Napisałem kod na 72pkt, gdzie dzielę graf na SCC 2 dfs-ami jeden, żeby ustalić kolejnośc post order, potem odwracam krawędzie i w tej kolejności post order odpalam DFS-y i to są silnie spójne składowe. Żeby odwrócić krawędzie muszę zrobić vector vectorów, a limit to 32MB, próbowałem też na multisecie trzymać krawędzie postaci a->b, ale to też zawolne. Nie wiem co zrobić dalej, bo problemem jest też to jak zliczyć ile jest krawędzie w tym grafie silnie spójnych składowych.

Z góry dziękuję za pomoc!

Comments

To się da rozwiązać dużo prościej bez SCC. Rozrysuj sobie graf jaki powstanie i zobacz jaki będzie miał kształt

Answer 1

 Whistleroosh zrobiłem, to bardzo fajnym pomysłem (pewnie chodziło Ci o to samo), dzięki za hinta, tak to bym pewnie się pomęczył i zaklepał SCC, a tak to poznałem bardzo fajny sposób, opiszę krótko rozwiązanie, jakby ktoś kiedyś się męczył. Mianowicie:

Zastanówmy się co oznacza nasza krawędź i -> j, w grafie. Oznacza, że klucz i jest w skrzynce j, ale co kluczowe jeśli mamy jakąś scieżkę wierzchołków. Np:  

To otwierając skrzynkę w wierzchołku żółtym otworzymy wszystkie wierzchołki na ścieżce, które idą do niego! Nigdy nie opłaca nam się otworzyć w którymś czarnym wierzchołku, skoro mozna otworzyć w żółtym i mieć to samo co w czarnym + dodatkowe. Zauważmy, że całośc polega, na podzieleniu grafu, na pod drzewa, tak, żeby w podrzewie było jak najwięcej wierzchołków. A to robimy już bardzo prosto, idziemy sobie DFS-em i jeśli natkniemy się na inne poddrzewo, to poprostu dołączamy całą ścieżkę sprawdzaną do tego podrzewa, i nic nie dodajemy do wyniku. Natomiast, jeśli natkniemy się na podrzewo aktualne (te co mamy na ścieżce sprawdzanej), to znaczy, że tworzymy nowe podrzewo i wyn++.

O(N), bo każdy wierzchołek maksymalnie raz odwiedzimy. Kod bardzo skomplikowany, wystarczy jednego DFS-a puścić ;), koło 10 linii, oprócz wczytania danych i wypisania, includów, deklaracji zmiennych / vectorów itp. :)

#include <iostream>
#include <vector>

using namespace std;

int n = 0, wczytana_liczba = 0, wyn = 0, numer_spojnej = 0;
vector<int> krawedz;
vector<int> w_jakiej_spojnej;

void DFS(int v)
{
    w_jakiej_spojnej[v] = numer_spojnej;
    if (w_jakiej_spojnej[krawedz[v]] == -1)
        DFS(krawedz[v]);
    else if (w_jakiej_spojnej[krawedz[v]] == numer_spojnej)
        wyn++;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    krawedz.assign(n+1,0);
    w_jakiej_spojnej.assign(n+1,-1);
    for (int i = 0; i < n; ++i)
    {
        cin >> wczytana_liczba;
        krawedz[i+1] = wczytana_liczba;
    }
    for (int i = 1; i <= n; ++i)
    {
        if (w_jakiej_spojnej[i] == -1)
        {
            DFS(i);
            numer_spojnej++;
        }
    }
    cout << wyn << '\n';

    return 0;
}

Przykładowe drzewa, jeśli wynik jest 2. (Wynik to zawsze liczba drzew). Na żółto korzenie drzewa

Bardzo podobne jest zadanie Speedrun z 2 etapu XIV OIJ. Jest wątek na forum.

Jeszcze raz dzięki za hinta. Tobie też chodziło o to samo, czy jest jakiś inny pomysł oprócz tego / SCC?

Comments

Tak, mniej więcej chodziło mi o to samo. Ogólnie warto pamiętać że graf w którym z każdego wierzchołka wychodzi dokładnie jedna krawędź ma charakterystyczny kształt. Każda spójna to po prostu jeden cykl z drzewami ukorzenionymi na którymś wierzchołku z cyklu

---

Tę wersję z SCC dałoby sie pewnie poprawić żeby weszło na 100. Brakowało pamięci pewnie przez rekurencje dfs'a, więc wystarczyło go zrobić iteracyjnie

---

Tylko tam był problem, że jak odwracasz krawędzie do 2 DFS-a to musi być już vector vectorow i na starcie 20MB, bo N do miliona. A set też nie wyrabiał pamięciowo.