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?