Vašou úlohou bolo zistiť, či vieme orientovať cesty tak, aby z každého mesta vychádzala aspoň jedna cesta. Tí z vás, ktorí už počuli o grafoch, si určite všimli, že túto úlohu vieme reprezetovať pomocou grafu, kde mestá sú vrcholy a cesty sú hrany. V ďalšom texte teda budeme pre jednoduchosť používať grafovú terminológiu. V grafovej terminológii teda zadanie úlohy znie, že máme zistiť, či vieme orientovať hrany v neorientovam grafe tak, aby z každého vrcholu vychádzala aspoň jedna hrana.

Pozorovania

Dôležitým pozorovaním pri riešení tejto úlohy je, že si môžeme graf rozdeliť na komponenty súvislosti a každý komponent súvislosti skúmať samostatne. Je to preto, lebo to, či vieme správne orientovať hrany v jednom komponente nijako neovplyvňuje ostatné komponenty. Ak aspoň v jednom komponente nevieme orientovať hrany podľa zadania, tak potom je odpoveď nie. Vďaka tomuto sa môžeme v ďalšom texte zoberať iba grafmi, ktoré sú tvorené presne jedným komponentom súvislosti.

Začnime riešenie úlohy tak, že si napíšeme niektoré prípady, kedy učite nevieme hrany orientovať podľa zadania. Ak máme jeden komponent súvislosti, ktorý sa skladá z jediného samostatného vrcholu, do ktorého nejdú žiadne hrany, tak v ňom určite nevieme orientovať hrany podľa zadania (tento vrchol nemá žiadnu hranu, takže z neho nemá aká vychádzať). Rovnako, ak napríklad máme komponent, ktorý sa skladá presne z dvoch vrcholov spojených hranou, z jedného z nich hrana vychádzať nemôže.

Ak si takto rozoberieme ešte niekoľko prípadov zistíme, že ak je komponent grafu strom, tak v ňom nevieme orientovať hrany podľa zadania. Predstavme si totiž ľubovoľný zakorenený strom. Ak v ňom orientujeme hrany zvrchu dole (od koreňa), tak žiadna hrana nebude vychádzať z listov. Ak orientujeme hrany opačne (od listov), tak žiadna hrana nebude vychádzať z koreňa. A samozrejme, ak orientujeme hrany hocijako inak, tak niekde v strede grafu nám vznikne vrchol/vrcholy, z ktorých žiadna hrana nevychádza.

Hlavná myšlienka

Už vieme, že ak je komponent grafu strom, tak v ňom nevieme zorientovať hrany podľa zadania. Otázka je, že či vo všetkých ostatných druhoch grafov vieme správne zorientovať hrany. Odpoveď je áno. Stačí ak doplníme do stromu na akékoľvek miesto jednu hranu. Potom môžeme strom zakoreniť v jednom z týchto vrcholov, kam sme pridali hranu. Teraz sa dajú v strome všetky hrany orientovať z listov smerom hore. To znamená, že ak by náš graf bol strom (bez pridanej hrany), tak jediný vrchol z ktorého by nevychádzala hrana by bol koreň. Do koreňa vedie ale ešte jedna hrana naviac (tá, ktorá je v grafe naviac oproti stromu). Túto hranu vieme orientovať smerom z koreňa. Z vrcholu kam hrana vedie už nejaká hrana vychádza (ide smerom hore do jeho rodiča), takže tým nič nepokazíme.

Postup sa teda dá zhrnúť takto: - rozdelíme si graf na komponenty súvislosti - prejdeme všetky komponenty súvislosti a ak každý obsahuje oproti stromu aspoň jednu hranu naviac, tak odpovedáme ano - inak odpovedáme nie

Ako nájsť “hrany naviac”?

Teraz sa pozrime na to, ako zistiť, či graf obsahuje nejakú “hranu naviac” oproti stromu. Predstavme si napríklad, ako prehľadáva tento strom prehľadávanie do hĺbky. Toto prehľadávanie postupne prechádza všetky vrcholy a v každom vrchole sa pozrie na všetkých jeho susedov. Týchto susedov môžeme rozdeliť do troch kategórií. Susedný vrchol môže byť: - ešte nenavštívený - ten vrchol z ktorého sme do aktuálneho vrcholu prišli (a teda je navštívený) - hociktorý iný už navštívený vrchol

Ak si predstavíme ako postupne prechádza prehľadávanie do hĺbky stromom, tak každú hranu v strome vidíme dva krát: raz, keď po nej ideme do nového vrcholu a druhý krát, keď by sme sa po nej vrátili do vrcholu z ktorého sme do aktuálneho vrcholu prišli (vedie do rodiča aktuálneho vrcholu). Tieto dva prípady zodpovedajú prvým dvom kategóriám susedných vrcholov.

Ak máme v grafe nejakú hranu naviac oproti stromu, tak táto hrana nevedie do nového vrcholu a ani nevedie do rodiča aktuálneho vrcholu (keďže podľa zadania môžeme predpokladať, že v grafe neexistujú násobné hrany).

Hrany naviac teda vieme nájsť pomerne jednoducho: stačí spustiť prehľadávanie do hĺbky z ľubovoľného vrcholu. V každom vrchole si potrebujeme pamätať z ktorého vrcholu sme sa do aktuálneho vrcholu dostali (nášho rodiča). Ak nájdeme susedný vrchol, ktorý je už navštívený a nie je to náš rodič, tak sme našli “hranu naviac” a vieme, že v tomto komponente vieme zorientovať hrany podľa zadania.

Zhrnutie a zložitosti

Ako sme už písali vyššie, tak postupne prechádzame všetky komponenty súvislosti grafu a o každom sa rozhodujeme samostatne. Ak každý komponent súvislosti obsahuje oproti stromu aspoň jednu hranu naviac, tak odpovedáme ano, inak odpovedáme nie. To, že či komponent obsahuje nejakú hranu naviac oproti stromu zisťujeme prehľadávaním do hĺbky.

Tento program si okrem pár premenných potrebuje pamätať vstupný graf, ktorý obsahuje $n$ vrcholov a $m$ hrán, takže pamäťová zložitosť je $O(n+m)$. Čo sa týka časovej zložitosti, tak na grafe niekoľko krát (pre každý komponent jeden krát) spustíme prehľadávanie do hĺbky. Je dobré si uvedomiť, že nezáleží na tom, koľko komponentov súvislosti vlastne graf obsahuje. Na určenie časovej zložitosti stačí, že vieme, že dokopy vo všetkých prehľadávaniach prejdeme celý graf (budeme v každom vrchole presne raz a na každú hranu sa pozrieme konštantný počet krát). Časová zložitosť je teda $O(n+m)$.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<vector<ll> > G;
vector<bool> visited;

bool dfs(ll v, ll parent){
    bool answer = false;
    visited[v] = true;
    for(ll i=0;i<G[v].size();i++){
        ll u = G[v][i];
        if(u!=parent && visited[u])
            answer = true;
        if(!visited[u]){
            answer = dfs(u, v) || answer;
        }
    }
    return answer;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    ll n, m;
    cin >> n >> m;
    G.resize(n);
    visited.resize(n, false);

    for (ll i=0;i<m;i++){
        ll a, b;
        cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    for(ll i = 0; i<n; i++){
        if(!visited[i]){
            if(!dfs(i, -1)){
                cout<<"nie"<<endl;
                return 0;
            }
        }
    }
    cout<<"ano"<<endl;
    return 0;
}

from sys import setrecursionlimit

setrecursionlimit(1000000)

def dfs(v, parent):
    answer = False
    visited[v] = True
    for u in G[v]:
        if u!=parent and visited[u]:
           answer = True
        if not visited[u]:
            answer = dfs(u, v) or answer 
    return answer

def solve():
    for i in range(n):
        if not visited[i]:
            result = dfs(i, -1)
            if not result:
                print("nie")
                return
    print("ano")

n, m = map(int, input().split())
G = [[] for _ in range(n)]
visited = [False for _ in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

solve()