Zadanie

Krtko sa chce dostať z tej masívnej KSP párty domov, ale keďže sa prejedol torty, tak sa len tak kotúľa. Snaží sa kráčať, no každým krokom sa bojí, že sa preváži a spadne. Preto, koľko krokov spraví pravou nohou, toľko ich musí spraviť aj ľavou, aby to nejak vybalansoval. Ale keďže je hrooozne najedený, tak sa nechce úplne nachodiť.

Úloha

Daný je graf s \(n\) vrcholmi, očíslovanými od \(1\) po \(n\), ktorého vrcholy reprezentujú Krtkove pozície na ceste domov po krokoch – čo vrchol, to krok (kam Krtko spraví krok, tam sa posunie celým telom; nemôže byť nohami v dvoch vrcholoch naraz). V grafe sú samozrejme aj nejaké iné možnosti krokov, kam nie nutne musí stúpiť. Hrana z \(a\) do \(b\) znamená, že z vrcholu \(a\) vie do \(b\) prejsť na jeden krok.

Nájdite cestu párnej dĺžky z vrcholu číslo \(1\) (miesto, kde bola párty) do vrcholu číslo \(n\) (miesto, kde Krtko býva), kratšiu ako \(2n\) (nechce sa predsa nachodiť). Krtko sa samozrejme ale vie stratiť a zamotať, a teda môže prejsť v grafe cez vrchol aj viackrát a po hranách tiež.

Formát vstupu

V prvom riadku vstupu sú čísla \(n\) (\(1 \leq n \leq 10^5\)) počet vrcholov, a \(m\) (\(1 \leq m \leq 10^6\)) počet hrán.

Nasleduje \(m\) riadkov popisujúcich hrany. V každom z nich sú dve čísla oddelené medzerou, čísla vrcholov medzi ktorými je hrana.

Pre sady vstupov platia nasledovné obmedzenia:

Sada 1 2 3 4
\(n \leq\) \(10\) \(100\) \(1\,000\) \(10^5\)
\(m \leq\) \(10\) \(1\,000\) \(10^4\) \(10^6\)

Formát výstupu

Na jeden riadok vypíšte zaradom čísla vrcholov cez ktoré Krtkova cesta prechádza – do ktorých Krtko spraví krok, oddelené medzerou (vrátane vrcholu \(1\) a \(n\)). Ak žiadna vyhovujúca postupnosť neexistuje vypíšte \(-1\).

Príklady

Input:

6 6
1 6
3 2
2 4
5 4
4 3
3 6

Output:

1 6 3 2 4 3 6

Input:

6 6
1 2
2 3
3 4
2 5
3 6
5 6

Output:

-1

V tejto úlohe sme mali zadaný graf na \(n\) vrcholoch. Zaujímalo nás nájdenie takej cesty z vrchola 1 do vrchola \(n\), ktorá má párnu dĺžku menšiu ako \(2n\).

Pomalé riešenie

Zadanie úlohy vyzerá takmer ako bežné hľadanie najkratšej cesty. Jediným problémom je, že naša cesta musí mať párnu dĺžku.

Môžeme teda spraviť nasledovný trik. Vyrobíme si nový graf na vrcholoch 1 až \(n\). V tomto novom grafe bude hrana medzi každou dvojicou vrcholov \(a\), \(b\) takou, že v pôvodnom grafe boli \(a\), \(b\) vo vzdialenosti 2. Inak povedané, každá hrana v novom grafe bude predstavovať dve hrany pôvodného grafu.

Keď teraz nájdene najkratšiu cestu mezdi vrcholmi 1 a \(n\) v novom grafe, bude mať nejakú dĺžku \(d\). Táto cesta bude zodpovedať ceste dĺžky \(2d\) v pôvodnom grafe. Ak je \(2d < 2n\), našli sme vyhovujúce riešenie. Na hľadanie najkratšej cesty môžeme použiť vhodné prehľadávanie grafu.

Toto riešenie bude mať časovú zložitosť \(O(n^3)\) kvôli vytváraniu nového grafu.

import sys
sys.setrecursionlimit(200000)

def dfs(a):
    # print('a n:',a,n)
    if visited[a] == True:
        return []
    if a == v-1:
        return [a]
    visited[a] = True
    for b,c in G2[a]:
        res = dfs(b)
        if len(res) > 0:
            res.append(c)
            res.append(a)
            return res
    return []

v, e = map(int, input().split())
G = [[] for i in range(v)]
for i in range(e):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

G2 = [[] for i in range(v)]
for a in range(v):
    for b in G[a]:
        for c in G[a]:
            if b < c:
                G2[b].append((c,a))
                G2[c].append((b,a))


visited = [False for i in range(v)]
res = dfs(0)
if len(res) == 0:
    print(-1)
else:
    print(*map(lambda x: x+1, reversed(res)))
#include <iostream>
#include <vector>

using namespace std;

int v,e;
vector<vector<pair<int, int>>> G2;
vector<bool> visited;

vector<int> dfs(int a){
    //# print('a n:',a,n)
    vector<int> res;
    if (visited[a] == true)
        return res;
    if (a == v-1){
        res.push_back(a);
        return res;
    }
    visited[a] = true;
    for (auto bc : G2[a]){
        int b = bc.first;
        int c = bc.second;
        res = dfs(b);
        if (res.size() > 0){
            res.push_back(c);
            res.push_back(a);
            return res;
        }
    }
    return res;
}

int main(){
   
    cin >> v >> e;
    vector<vector<int>> G(v);
    for (int i=0; i<e; i++){
        int a,b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    G2.resize(v);
    for (int a=0; a<v; a++)
        for (auto b : G[a])
            for (auto c : G[a])
                if (b < c){
                    G2[b].push_back({c,a});
                    G2[c].push_back({b,a});
                }


    visited.resize(v,false);
    vector<int> res = dfs(0);
    if (res.size() == 0)
        cout<<"-1"<<endl;
    else{
       cout<<res[res.size()-1]+1;
        for (int i=res.size()-2; i>=0; i--)
            cout<<' '<<res[i]+1;
        cout<<endl;
    }
}

Štandardná úloha

Táto úloha je celkom štandardná. Pri bežnom hľadaní najkratšej cesty si v každom vrchole pamätáme najmenšiu vzdialenosť, na ktorú sa do daného vrchola vieme dostať zo zdroja. My si ale v každom vrchole budeme pamätať dve informácie. Jedna z nich bude predstavovať najmenšiu párnu vzdialenosť, na ktorú sa do daného vrchola vieme dostať. Druhá bude analogicky predstavovať najmenšiu nepárnu vzdialenosť do daného vrchola zo zdroja.

Obe tieto informácie vieme počas prehľadávania grafu jednoducho aktualizovať. Princíp je rovnaký, ako pri obyčajnom BFS.

Netreba najkratšiu cestu

Zadanie od nás vyžaduje iba nájsť nejakú nie príliš dlhú párnu cestu. Namiesto BFS teda môžeme použiť aj DFS. Opäť budeme mať 2 kópie pôvodného grafu. Jednu nazveme nepárna, druhú párna. V každom kroku DFS sa presunieme do susedného vrchola, avšak v opačnej kópii. Prehľadávanie začneme v jednej z kópií vo vrchole 1. Ak sa nám podarí dostať do vrchola \(n\) v tej istej kópií, našli sme párnu cestu.

Ak niekedy počas prehľadávania prejdeme už viac, ako \(2n\) vrcholov, nevnoríme sa ďalej, pretože by takáto cesta bola príliš dlhá.

Takéto riešenie má časovú aj pamäťovú zložitosť \(O(n + m)\).

import sys
sys.setrecursionlimit(200000)

def dfs(a, n):
    # print('a n:',a,n)
    if visited[n][a] == True:
        return []
    if n == 0 and a == v-1:
        return [a]
    visited[n][a] = True
    for b in G[a]:
        res = dfs(b, n^1)
        if len(res) > 0:
            res.append(a)
            return res
    return []

v, e = map(int, input().split())
G = [[] for i in range(v)]
for i in range(e):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

visited = [[False for i in range(v)], [False for i in range(v)]]
res = dfs(0,0)
if len(res) == 0:
    print(-1)
else:
    print(*map(lambda x: x+1, reversed(res)))
#include <iostream>
#include <vector>

using namespace std;

vector<vector<bool>> visited(2);
int v, e;
vector<vector<int>> G;


vector<int> dfs(int a, int n){
    //# print('a n:',a,n)
    vector<int> res;
    if (visited[n][a] == true)
        return res;
    if (n == 0 and a == v-1){
        res.push_back(a);
        return res;
    }
    visited[n][a] = true;
    for(auto b : G[a]){
        res = dfs(b, n^1);
        if (res.size() > 0){
            res.push_back(a);
            return res;
        }
    }
    return res;
}

int main(){
    cin >> v >> e; 
    G.resize(v);

    for (int i=0; i<e; i++){
        int a, b;
        cin >> a >> b;
        a -= 1;
        b -= 1;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    visited[0].resize(v,false);
    visited[1].resize(v,false);
    vector<int> res = dfs(0,0);
    if (res.size() == 0)
        cout<<"-1"<<endl;
    else {
        cout<<res[res.size()-1]+1;
        for (int i=res.size()-2; i>=0; i--)
            cout<<' '<<res[i]+1;
        cout<<endl;
    }
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.