5. Cyklus v potrubí vzorové riešenie

3 3
0 1 KSP
1 2 nic
2 0 nic

obsahuje

3 3
0 1 KSP
1 2 nic
2 1 nic

NEobsahuje

Začnime tým, že si formálnejšie pomenujeme, čo presne je zadaním tejto úlohy. Na vstupe máme systém potrubí, ktorý spolu tvorí graf. Vieme, že potrubie je trochu iné ako bežne poznáme – voda cez potrubie vie tiecť iba jedným smerom. To znamená, že graf, ktorý reprezentuje potrubie je orientovaný. Niektoré potrubia sú špeciálne, keďže sa na ich stene nachádza KSP logo.

Našou úlohou je zistiť, či v potrubí existuje taká postupnosť potrubí (ktorá začína na spojení číslo \(0\)), ktorá obsahuje logo KSP a zároveň po nej voda vie chodiť donekonečna. To znamená, že máme zistiť, či graf obsahuje cyklus, ktorý obsahuje hranu, ktorá má na sebe KSP logo. Tento cyklus ale musí byť dosiahnuteľný z vrcholu \(0\).

Existuje cyklus, ktorý prechádza cez túto hranu?

Predstavme si, že máme zistiť, či v grafe existuje cyklus, ktorý obsahuje nejakú konkrétnu hranu. Povedzme, že táto hrana vedie z vrcholu \(u\) do vrcholu \(v\). To, čo nám stačí urobiť je, že spustíme nejaké naše obľúbené prehľadávanie z vrcholu \(v\) (z konca hrany), a budeme zisťovať, že či sa počas prehľadávania dostaneme do vrcholu \(u\), teda na začiatok hrany. Ak sa dostaneme, tak to znamená, že sa z vrcholu \(u\) vieme dostať do vrcholu \(v\), odkiaľ sa našou hranou vieme dostať zase do vrcholu \(u\), a teda v grafe existuje cyklus, ktorý obsahuje túto hranu.

To je už takmer to, čo potrebujeme zistiť. Jediná drobnosť ktorá chýba, je overiť, že či sa vieme k tomuto cyklu dostať z vrcholu \(0\). To vieme tiež urobiť tak, že spustíme naše obľúbené prehľadávanie z vrcholu \(0\). Ak sa nám týmto prehľadávaním podarí dosiahnuť vrchol \(u\) (alebo \(v\)), tak je celý cyklus dosiahnuteľný z vrcholu \(0\).

Týmto už máme všetky ingrediencie na prvé riešenie. Tým riešením je, že prejdeme cez všetky hrany s KSP logom. Pre každú z nich zistíme, či sa z koncového vrcholu tejto hrany vieme dostať do počiatočného. Ak áno, tak zistíme, že či je tento cyklus dosiahnuteľný z vrcholu \(0\). V prípade, že toto platí aspoň pre jednu hranu zo vstupu, tak je odpoveď obsahuje, inak je odpoveď NEobsahuje.

Keďže hrán s KSP logom môže byť najviac \(m\), a pre každú z nich v najhoršom prípade prehľadáme celý graf (v zložitosti \(O(n+m)\)), tak celková zložitosť je najviac \(O(m(n+m))\). Pamätať si okrem vstupného grafu nemusíme nič, takže pamäťová zložitosť zostáva \(O(n+m)\).

Detekcia cyklov s nejakými špeciálnymi hranami, to mi znie nejako povedome…

Ďalšie riešenie je založené na nasledujúcej myšlienke: V prípade, že ste niekedy počuli o Dijkstrovom alebo Floyd-Warshallovom algoritme, tak ste možno počuli o problémoch, ktoré nastávajú ak v grafe v ktorom zisťujeme vzdialenosti sú medzi vrcholmi záporné hrany (hrany so zápornou dĺžkou).

Konkrétnejšie, teraz nás bude zaujímať to, že občas sa nám môže stať, že v grafe existuje záporný cyklus (cyklus so zápornou dĺžkou). Ten môže spôsobiť, že najkratšia cesta medzi vrcholom \(a\) a \(b\) obsahuje tento cyklus, a teda dĺžka najkratšej cesty je rovná \(-\infty\) (keďže najkratšia cesta obsahuje nekonečno prejdení záporného cyklu).

Takéto niečo je ale veľmi podobné tomu, čo máme zistiť. Chceli by sme vedieť, že či na ceste z vrcholu \(0\) do nejakého iného vrcholu existuje cyklus, ktorý obsahuje špeciálnu hranu (zápornú hranu, resp. hranu s KSP logom).

To, čo teda vieme urobiť je, že zo vstupného grafu urobíme ohodnotený graf. To urobíme tak, že hrany, ktoré neobsahujú KSP logo ohodnotíme nejakým malým kladným číslom – napríklad \(1\). Hrany, ktoré obsahujú KSP logo ohodnotíme \(-\infty\), resp. dostatočne veľkým záporným číslom.

Potom spustíme nejaké prehľadávanie z vrcholu \(0\), a ak nájdeme nejaký záporný cyklus, tak môžeme vyhlásiť, že potrubie obsahuje cyklus s nápisom KSP.

Záporné cykly vieme napríklad detegovať Floyd-Warshallovovym algoritmom, a to tak, že najprv spustíme tento algoritmus, ktorý nájde najkratšie vzdialenosti medzi každou dvojicou vrcholov. Záporný cyklus sa nám na výsledných vzdialenostiach prejaví tak, že najkratšia vzdialenosť z vrcholu do samého seba je záporná. Následne zistíme, či je nejaký z vrcholov, cez ktorý prechádza záporný cyklus dosiahnuteľný z vrcholu \(0\).

Floyd-Warshallov algoritmus má časovú zložitosť \(O(n^3)\) a následne ešte potrebujeme prejsť celý graf, aby sme zistili, ktoré vrcholy sú dosiahnuteľné z vrcholu \(0\). Výsledná časová zložitosť je teda rovná \(O(n^3 + n+m) = O(n^3)\). Pamätať si okrem celého grafu potrebujeme ešte maticu vzdialeností medzi vrcholmi (ktorá síce môže byť porovnateľne veľká s počtom hrán, ale pre korektnosť ju spomíname). To znamená, že pamäťová zložitosť je \(O(n+m+n^2)\).

import sys
from math import inf

def dfs(v):
    for u in range(len(G[v])):
        if G[v][u]!=inf:
            if not visited[u]:
                visited[u] = True
                dfs(u)
    return False

n, m = map(int, input().split())
G = [ [ inf for i in range(n) ] for j in range(n) ]
visited = [ False for _ in range(n) ]
for i in range(n):
    G[i][i] = 0;

for i in range(m):
    v, u, sympaticka = input().split()
    v = int(v)
    u = int(u)
    if sympaticka=='KSP':
        G[v][u] = -inf
    else:
        G[v][u] = 1

for k in range(n):
    for i in range(n):
        for j in range(n):
            G[i][j] = min(G[i][j], G[i][k]+G[k][j])


dfs(0)

for i in range(n):
    if G[i][i]<0:
        if visited[i]:
            print("obsahuje")
            sys.exit(0)
print("NEobsahuje")

Vzorové riešenie

Ako na väčšinu takýchto úloh, vzorové riešenie je použiť prehľadávanie do hĺbky. Ako prvé si je treba uvedomiť, ako pri prehľadávaní do hĺbky vieme detegovať cykly.

Najprv si uvedomme, že počas prehľadávania grafu môžu byť vrcholy v trochu rôznych “stavoch”: nenavštívené, otvorené a zatvorené. Ako nenavštívené označujeme také vrcholy, že v nich sme ešte neboli (náš algoritmus ich nenavštívil), a ešte čakajú na svoje objavenie. Otvorenými, nazvime také vrcholy, že algoritmus aktuálne prehľadáva niektoré vrcholy v ich podstrome, teda že sme už tieto vrcholy objavili, ale ešte sme neprezreli všetky hrany, ktoré z nich vedú. Tretím druhom sú uzavreté vrcholy. To sú také, že sme už prezreli všetky hrany, ktoré z nich vedú a odišli sme z nich prehľadávať niečo iné (a už sa sem nikdy nevrátime).

Následne, podľa toho, do ktorého vrcholu smeruje hrana, DFS počas prehľadávania stromu nachádza \(3\) druhy hrán:

• dopredné/stromové. Tento druh hrán sa vyskytne vtedy, keď prejdením po tejto hrane prídeme do ešte neobjaveného vrcholu.

• spätné. Tento druh hrán sa vyskytne vtedy, keď hrana smeruje do otvoreného vrcholu. Môžete si rozmyslieť, že tento vrchol musí byť nejaký predok (v DFS strome) daného vrcholu..

• priečne/kolmé. Tento druh hrán smeruje do už uzatvorených vrcholov. Môžete si rozmyslieť, že tento vrchol nie je predok (v DFS strome) daného vrcholu.

V prípade, že by sa v grafe nevyskytovali žiadne cykly, tak by graf obsahoval iba dopredné a priečne hrany (opäť si premyslite prečo). Tá vec, ktorá nás teda pri hľadaní cyklov bude zaujímať je, že či v grafe existujú spätné hrany. V prípade, že v grafe existuje nejaká spätná hrana, tak v grafe existuje aj cyklus.

Otázka je, že ako zistiť, že či sa niekde na tomto cykle vyskytla hrana s nápisom KSP. Mohli by sme samozrejme nejako prejsť celú postupnosť hrán, a zisťovať, že či tam taká hrana nebola, ale ide to aj výrazne jednoduchšie. Stačí nám zaznamenávať si počet hrán s nápisom KSP, ktoré sme doteraz videli po ceste z vrcholu \(0\). V prípade, že nájdeme spätnú hranu, tak nám stačí zistiť, koľko hrán s nápisom sme videli po ceste do vrcholu, kde aktuálne sme, a koľko ich bolo vo vrchole, kam vedie spätná hrana. Ak sa tento počet líši (alebo má samotná spätná hrana nápis), tak sa niekde na cykle musela vyskytnúť spätná hrana.

Takéto riešenie okrem bežného DFS robí pre každý vrchol iba konštantne viac operácií, a teda celý algoritmus beží v zložitosti ako bežné DFS, teda \(O(n+m)\). Pamätať si potrebujeme iba celý vstupný graf, a teda zložitosť je \(O(n+m)\).

import sys
from math import inf

sys.setrecursionlimit(10000)

def dfs(v):
    doteraz_sympatickych = sympaticke[v]
    visited[v] = None
    for u, sympaticka in G[v]:
        if visited[u] is False:
            sympaticke[u] = doteraz_sympatickych+int(sympaticka)
            if dfs(u):
                return True
        elif visited[u]==None and sympaticke[u] < doteraz_sympatickych+int(sympaticka):
            return True
    visited[v] = True
    return False

n, m = map(int, input().split())
G = [ [] for j in range(n) ]
visited = [ False for _ in range(n) ]
sympaticke = [ 0 for _ in range(n) ]

for i in range(m):
    v, u, sympaticka = input().split()
    v = int(v)
    u = int(u)
    sympaticka = sympaticka=='KSP'
    G[v].append((u, sympaticka))
    
visited[0] = None
sympaticke[0] = 0
if dfs(0):
    print("obsahuje")
else:
    print("NEobsahuje")

#include<iostream>
#include<vector>
#include<string>

# define NOT_VISITED 0
# define OPEN 1
# define CLOSED 2 

using namespace std;

vector<vector<pair<long long, long long> > > G;
vector<long long> sympaticke;
vector<int> visited;

bool dfs(long long v){
    visited[v] = OPEN;
    long long doteraz_sympatickych = sympaticke[v];
    for(auto & i : G[v]){
        long long u = i.first;
        bool sympaticka = i.second;
        if(visited[u]==NOT_VISITED){
            sympaticke[u] = doteraz_sympatickych + sympaticka;
            if(dfs(u))
                return true;
        } else if(visited[u]==OPEN && sympaticke[u]<doteraz_sympatickych+sympaticka){
            return true;
        }
    }
    visited[v] = CLOSED;
    return false;
}

int main(){
    long long n, m;
    cin>>n>>m;

    G.resize(n);
    sympaticke.resize(n, 0);
    visited.resize(n, NOT_VISITED);

    for(long long i=0;i<m;i++){
        long long u, v;
        string sympaticka;

        cin>>u>>v>>sympaticka;

        G[u].push_back({v, "KSP"==sympaticka});
    }

    sympaticke[0] = 0;
    if(dfs(0))
        cout<<"obsahuje"<<endl;
    else
        cout<<"NEobsahuje"<<endl;

    return 0;
}