Skúšame všetky možnosti

Nič nepokazíme hrubou silou: vygenerujeme všetky možné rôzne poradia miest, tých je $n\times (n-1) \times \dots 1 = n!$, napríklad pomocou next_permutation alebo itertools.permutations(), a pre každé takéto poradie overíme, či spĺňa podmienku. Konkrétne si pre každé poradie vieme postupne simulovať vypínanie miest.

Po každom odpojení prvých $1 \leq i\leq n - 1$ miest, si treba overiť, či všetky zostávajúce mestá sú stále spojené s elektrárňou. Ako prvé skontrolujeme, či sme náhodou neodpojili aj ju (ak áno, musí byť posledné vypnuté mesto v poradí).

Následne si vieme spustiť prehľadávanie grafu z elektrárne (DFS alebo BFS, viď kuchárku). Potom si len stačí overiť, či sme každé miesto už buď odpojili, alebo navštívili.

Pre každé možné poradie spustíme $n$-krát prehľadávanie celého grafu, ktoré zaberie v najhoršom prípade $O(n+m)$ času. Poradí je $n!$, takže časová zložitosť je $O(n! \cdot n \cdot (n + m))$. Pamäťová zložitosť je $O(n + m)$, keďže si musíme náš graf celý pamätať.

Krok ku riešeniu

Všimnite si, že už len zisťovanie, či nejaké poradie funguje nám zaberie kvadratický čas – $O(n(n+m))$, čo je príliš veľa.

Skúsme, namiesto tipovania riešení a skúšania či fungujú, sa zamyslieť nad tým aké riešenia určite fungovať budú. Všimnime si, že mesto ktoré odstránime posledné vieme – je ním mesto, v ktorom je elektráreň. Nazvime ho $a_n$.

Čo vieme povedať o meste, ktoré odpojíme ako predposledné? Zjavne musí priamo susediť s elektrárňou, inak by stratilo prúd skôr než ho odpoja.

Zoberme si teda akékoľvek mesto súvisiace s elektrárňou, nazvime ho $a_{n-1}$.

Keď už máme mestá ktoré odpojíme ako posledné a predposledné ($a_n$ a $a_{n-1}$), nájdeme si mesto, ktoré odpojíme ako pred-predposledné, následne nájdeme to pred-pred-posledné, a tak ďalej.

Inak povedané, postupnosť zostavujeme odzadu. A teda namiesto toho, aby sme mestá odstraňovali, budeme mestá postupne pridávať. A chceme ich pridávať tak, aby sieť, ktorú si postupne budujeme, bola vždy súvislá, a nachádza sa v nej elektráreň.

Druhú podmienku, ako sme si už povedali hore, splníme tak, že poslednú vždy odstránime elektráreň. Ako splníme prvú podmienku? Jednoducho, keď pridávame mesto $a_i$, pridáme mesto ktoré sme ešte nepridali (nie je medzi $a_{i+1},\cdot a_n$), ale ktoré je priamo spojené s niektorým $a_{i+j}$.

Na základe tohto nápadu vieme implementovať riešenie bežiace v $O(n \cdot (n+m))$: najskôr nadstavíme $a_n=k$ (mesto s elektrárňou). Potom, budujeme postupnosť odzadu: ak už máme $a_n, a_{n-1},\dots, a_{i+1}$, si prejdeme susedov týchto miest, a nájdeme takého ktorý sa ešte v postupnosti nenachádza. Zakaždým prejdeme najviac $m$ hrán, takže dostaneme horeuvedenú časovú zložitosť.

Vzorové riešenie

Odtiaľto sme už len kúsok od vzorového riešenia. Všimnite si, že v riešení hore pozeráme na hrany viackrát. Stačilo by nám, napríklad, si vždy keď do postupnosti pridáme nové $a_i$, si jeho susedov pridať do fronty (alebo zásobníka). Potom, keď hľadáme nový vrchol do postupnosti, prejdeme si túto frontu (zásobník) vrcholov. Ak sme už vrchol dali do postupnosti, odstránime ho z fronty (zásobníku) a túto hranu už nikdy neuvidíme – nemusíme.

Ak sme ešte vrchol nevideli, nastavíme ho ako nový člen postupnosti a pridáme jeho susedov do fronty (zásobníku).

Takto robíme to, čo predtým, len efektívnejšie: ku každému susedovi sa dostaneme maximálne raz, ale zároveň, keďže je naša mestská sieť súvislá, určite naplníme celú postupnosť. Takto teda dostaneme riešenie bežiace v časovej a aj pamäťovej zložitosti $O(n + m)$.

A nielen to! Záležiac od toho akú dátovú štruktúru ste použili, naprogramovali ste vlastne BFS (v prípade fronty), alebo DFS (v prípade zásobníka)!

Prečo toto riešenie vždy

funguje?

Pozrime sa napokon na to, prečo je takáto postupnosť odpájania $a_1,\dots,a_n$ v súlade s požiadavkami zo zadania.

1. Zachovanie spojitosti: Keď vypíname mestá v reverznom poradí akom sme ich pridávali (čiže od $a_1$ po $a_k$), vždy vypneme najskôr tie mestá, ktoré boli pridané ako posledné pri budovaní siete. Ale pridávali sme ich predsa tak, aby mestá $a_i,a_{i+1},\dots,a_n$ boli súvislé, čiže vypnutie prvých $i$ miest nikdy nepreruší spojenie medzi elektrárňou a zvyšnými mestami.

2. Elektráreň posledná: Keďže sme začali prehľadávanie v elektrárni, tá sa automaticky stane prvým prvkom v poradí návštev, a teda posledným prvkom v poradí vypínania.

3. Úplné pokrytie: Elektrická sieť je súvislá, takže ak nám ostávajú ešte nejaké mestá, je medzi nimi, a už pridanými mestami nejaká hrana.

n,m,k = map(int,input().split())
susedia = [[] for _ in range(n)]

for _ in range(m):
    a,b = map(int, input().split())
    susedia[a].append(b)
    susedia[b].append(a)

prejdeny = [False] * n
poradie = []
stack = [k]
prejdeny[k] = True

while stack:
    vrchol = stack.pop()
    poradie.append(vrchol)

    for sused in susedia[vrchol]:
        if not prejdeny[sused]:
            prejdeny[sused] = True
            stack.append(sused)

print(*reversed(poradie))

#include<bits/stdc++.h>

using namespace std;

#define FOR(i,n)    for(int i=0;i<(int)n;i++)
#define FOB(i,n)    for(int i=n;i>=1;i--)
#define MP(x,y) make_pair((x),(y))
#define ii pair<int, int>
#define lli long long int
#define ld long double
#define ulli unsigned long long int
#define lili pair<lli, lli>
#ifdef EBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif
#define SIZE(x) int(x.size())
const int infinity = 2000000999 / 2;
const long long int inff = 4000000000000000999;

typedef complex<long double> point;

template<class T>
T get() {
    T a;
    cin >> a;
    return a;
}

template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {
    out << "[" << par.first << ";" << par.second << "]";
    return out;
}

template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";
    out << "}";
    return out;
}

template <class T, class U>
ostream& operator<<(ostream& out, const map<T,U> &cont) {
    out << "{";
    for (const auto &x:cont) out << x << ", ";

    out << "}"; return out;
}

template <class T>
ostream& operator<<(ostream& out, const vector<T>& v) {
    FOR(i, v.size()){
      if(i) out << " ";
      out << v[i];
    }
    out << endl;
    return out;
}

bool ccw(point p, point a, point b) {
    if((conj(a - p) * (b - p)).imag() <= 0) return false;
    else return true;
}

void dfs(int v, vector<bool> &seen, vector<int> &poradie, vector<vector<int> >&hrany) {
    seen[v] = true;
    for (int w : hrany[v]) {
        if (!seen[w]) dfs(w, seen, poradie, hrany);
    }
    poradie.push_back(v);
}

int main() {
    cin.sync_with_stdio(false); cin.tie();
    cout.sync_with_stdio(false); cout.tie();
    int n = get<int>();
    int m = get<int>();
    int k = get<int>();
    vector<int> poradie;
    vector<bool> seen(n, false);
    vector<vector<int> > hrany(n);
    FOR(i, m) {
        int a = get<int>();
        int b = get<int>();
        hrany[a].push_back(b); hrany[b].push_back(a);
    }

    dfs(k, seen, poradie, hrany);
    FOR(i, n) {
        cout << (i ? " " : "") << poradie[i];
    }
    cout << endl;

}