Zadanie
Jedného dňa sa Marianka rozhodla osamostatniť a presťahovala sa do svojho vlastného bytu. Po pár dňoch bývania si uvedomila, že potrubie, ktoré vedie z jej záchoda, je pomerne opotrebované, a tak sa rozhodla ho vymeniť. Zavolala si majstrov z KSP (Komerční Smenári Potrubí) a tí jej ho bez meškania (rovnako ako robia všetky svoje povinnosti1) prišli vymeniť. Dokonca za veľmi výhodnú cenu Marianke ponúkli nové špeciálne jednosmerné potrubia, cez ktoré síce dokáže voda tiecť iba jedným smerom, ale za to sú masívne rýchle. Aby bolo jasné, kto túto prácu vykonal, vyrezali logo KSP do niekoľkých častí potrubia. Po pár dňoch práce bolo nové potrubie hotové a Marianka si mohla spokojne nažívať ďalej. Lenže, hneď pri prvom použití záchoda Marianka zistila, že odtekanie vody zo záchoda nie je až tak masívne rýchle, ako majstri z KSP prezentovali. Sklamaná z výsledku práce si zavolala na pomoc Sama s jeho inšpekčnou kamerou do potrubia. Keď sa do potrubia pozreli, tak zistili, že KSP robotníci z potrubia pod záchodom urobili hotový labyrint. Marianka kontaktovala KSP aby zistila, že prečo potrubie vyzerá tak, ako vyzerá. Zodpovední zamestanci jej odpovedali, že je to preto, aby sa mohla voda, ktorá odtečie zo záchodu nekonečne veľa krát pozrieť na nejaké z KSP lôg, ktoré sú na stenách niektorých potrubí.
Marianke sa ale nezdalo, že by potrubie reálne malo túto vlastnosť a teda chcela, aby jej Samo pomohol zistiť, že či je to naozaj tak. Samo je ale zaneprázdnený rozbehávaním vecí, a tak Marianke nezostalo nič iné ako túto úlohu zveriť Vám. Pomohli by ste Marianke zistiť odpoveď, aby bola opäť šťastná?
Úloha
Vašou úlohou je určiť, či sa v potrubí nachádza taká postupnosť potrubí, ktorá obsahuje logo KSP a zároveň po nej voda vie chodiť donekonečna. Táto postupnosť musí začínať v záchode, ktorý sa nachádza na spojení potrubí číslo \(0\). Nezabudnite, že potrubie pod záchodom je špeciálne – voda cez potrubie vie tiecť iba jedným smerom.
Formát vstupu
Na prvom riadku vstupu sa nachádzajú dve medzerou oddelené čísla \(n, m\), kde \(n\) označuje počet spojení potrubí a \(m\) označuje počet potrubí. Spojenia potrubí sú očíslované číslami od \(0\) po \(n-1\). Nasleduje \(m\) riadkov, kde sa na každom riadku nachádzajú \(3\) medzerou oddelené údaje: čísla \(u, v, 0\leq u,v < n\) označujúce čísla spojení potrubí, medzi ktorými potrubie vedie a reťazec \(s, s \in \{\texttt{nic}, \texttt{KSP}\}\), ktorý označuje, či sa v danom potrubí nachádza logo KSP alebo nič. Je garantované, že medzi dvomi spojeniami potrubia nevedie potrubie jedným smerom viac ako raz.
V jednotlivých sadách platia nasledujúce obmedzenia:
Sada | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
---|---|---|---|---|---|---|---|---|
\(1 \leq n \leq\) | \(20\) | \(100\) | \(120\) | \(125\) | \(800\) | \(1200\) | \(4000\) | \(6000\) |
Formát výstupu
Vypíšte jediný riadok, ktorý obsahuje reťazec obsahuje
v
prípade, že systém potrubí obsahuje takú postupnosť potrubí, ktorá
začína na spojení medzi potrubiami číslo \(0\), že voda môže donekonečna prechádzať
okolo niektorého KSP loga. V opačnom prípade vypíšte reťazec
NEobsahuje
.
Príklady
Input:
3 3
0 1 KSP
1 2 nic
2 0 nic
Output:
obsahuje
Input:
3 3
0 1 KSP
1 2 nic
2 1 nic
Output:
NEobsahuje
Týmto potrubím síce môže voda prúdiť donekonečna, ale logo KSP vie vidieť iba raz.
Exceptions may occur.↩︎
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]:
= True
visited[u]
dfs(u)return False
= map(int, input().split())
n, m = [ [ inf for i in range(n) ] for j in range(n) ]
G = [ False for _ in range(n) ]
visited for i in range(n):
= 0;
G[i][i]
for i in range(m):
= input().split()
v, u, sympaticka = int(v)
v = int(u)
u if sympaticka=='KSP':
= -inf
G[v][u] else:
= 1
G[v][u]
for k in range(n):
for i in range(n):
for j in range(n):
= min(G[i][j], G[i][k]+G[k][j])
G[i][j]
0)
dfs(
for i in range(n):
if G[i][i]<0:
if visited[i]:
print("obsahuje")
0)
sys.exit(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
10000)
sys.setrecursionlimit(
def dfs(v):
= sympaticke[v]
doteraz_sympatickych = None
visited[v] for u, sympaticka in G[v]:
if visited[u] is False:
= doteraz_sympatickych+int(sympaticka)
sympaticke[u] if dfs(u):
return True
elif visited[u]==None and sympaticke[u] < doteraz_sympatickych+int(sympaticka):
return True
= True
visited[v] return False
= map(int, input().split())
n, m = [ [] for j in range(n) ]
G = [ False for _ in range(n) ]
visited = [ 0 for _ in range(n) ]
sympaticke
for i in range(m):
= input().split()
v, u, sympaticka = int(v)
v = int(u)
u = sympaticka=='KSP'
sympaticka
G[v].append((u, sympaticka))
0] = None
visited[0] = 0
sympaticke[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;
long long, long long> > > G;
vector<vector<pair<long long> sympaticke;
vector<int> visited;
vector<
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);0);
sympaticke.resize(n,
visited.resize(n, NOT_VISITED);
for(long long i=0;i<m;i++){
long long u, v;
string sympaticka;
cin>>u>>v>>sympaticka;
"KSP"==sympaticka});
G[u].push_back({v,
}
0] = 0;
sympaticke[if(dfs(0))
"obsahuje"<<endl;
cout<<else
"NEobsahuje"<<endl;
cout<<
return 0;
}
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ť.