Tak jeszcze swoją drogą. Znalazłem dzisiaj ciekawy wykład z F&U - bardzo polecam: https://www.youtube.com/watch?v=EQIFihYife4 , dobrze tłumaczy zagadnienie. I zacząłem pisać kod z F&U i natknąłem się na bardzo ciekawy pomysł - trochę podmienienie tego z pomysłem F&U a mianowicie:
mamy 2 tablicę. Jedna to tablica kolory[k] oznaczająca jaka grupa odpowiada za dany kolor. Oraz tablicę vectorów zaleznosci, która mówi nam np grupa 2 jest zależna od grupy 4 (takie tak jakby F&U tylko nie przepinamy korzenia)
I jak dostajemy np 2->4 , to zmieniamy kolor[2] na 0 i kolor 4 zostawiamy jeśli tam coś jest i dopinamy - dodajemy zaleznosci[kolory[4]].push_back(kolory[2]), jak niema nic to poprostu zamianiamy kolory[4] = 2.
I w ten sposób na koniec algorytmu lecimy po kolorach od 1 do n i musimy odczytywać po zależnościach na kolejce tak jakby BFS-em. np dla i = 1. jak kolory[1] = 5, to oznacza ze grupa 5 i jej zaleznosci są odpowiedzialne za kolor 1. W ten sposób mamy O(n+m) złożonnośc zamortyzowana. Mój kod:
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n = 0;
int m = 0;
int k = 0;
cin >> n >> k >> m;
int samochody[n];
int kolory_po_zmianie[m + 1];
int kolory[m + 1];
vector<int> zaleznosci[m + 1];
for (int i = 0; i < n; ++i)
{
cin >> samochody[i];
}
for (int i = 0; i <= m; ++i)
{
kolory[i] = i;
kolory_po_zmianie[i] = i;
}
for (int i = 0; i < k; ++i)
{
int kolor_od = 0;
int kolor_do = 0;
cin >> kolor_od >> kolor_do;
if (kolory[kolor_od] == 0 || kolor_od == kolor_do)
{
continue;
}
else if (kolory[kolor_do] == 0)
{
kolory[kolor_do] = kolory[kolor_od];
kolory[kolor_od] = 0;
}
else
{
zaleznosci[kolory[kolor_do]].push_back(kolory[kolor_od]);
kolory[kolor_od] = 0;
}
}
for (int i = 1; i <= m; ++i)
{
queue<int> Q;
kolory_po_zmianie[kolory[i]] = i;
for (int j = 0; j < zaleznosci[kolory[i]].size(); ++j)
{
Q.push(zaleznosci[kolory[i]][j]);
kolory_po_zmianie[zaleznosci[kolory[i]][j]] = i;
}
while (!Q.empty())
{
for (int j = 0; j < zaleznosci[Q.front()].size(); ++j)
{
Q.push(zaleznosci[Q.front()][j]);
kolory_po_zmianie[zaleznosci[Q.front()][j]] = i;
}
Q.pop();
}
}
for (int i = 0; i < n; ++i)
{
printf("%d ",kolory_po_zmianie[samochody[i]]);
}
return 0;
}
Niestety dostaję 93pkt, bo mam jakiś błąd w odtczytywaniu (implementacja) (pewnie gdzies brakuje jakiegos if-a) i na 47 testów jeden ma przekroczenie limit czasu. (bardzo wczesny 5c.) Jak znajdę to zaktualizuję kod.
Ogólnie to całe zadanie, żeby zrobić w O(n+m) to strikte chyba na pomysł. Jak napiszę z F&U to też wrzucę.
Wyniki czasowe dla pozostałych testów minimalnie lepsze niż to rozwiązanie z zmienianiem czasu.