Poloměr komponent grafu
Zadání
V této úloze uvažujeme prosté neorientované grafy bez smyček. Pro přehlednost nejprve připomeneme standardní definice teorie grafů.
-
Cesta délky d (d ≥ 0) mezi uzly a a b v grafu G = (V, E) je taková neprázdná posloupnost jeho uzlů (a = x0, x1, x2, …, xd = b), ve které platí
-
0 < i ≤ d ⇒ {xi−1, xi} ∈ E.
-
0 ≤ i < j ≤ d ⇒ xi ≠ xj.
-
-
Graf G prohlásíme za souvislý, pokud mezi každými dvěma uzly v G existuje alespoň jedna cesta.
-
Komponenta grafu G je takový souvislý podgraf G, který není obsažen v žádném větším (vzhledem k inkluzi) souvislém podgrafu G.
-
Vzdálenost dvou uzlů v souvislém grafu je definována jako délka nejkratší cesty mezi nimi.
-
Excentricita uzlu v souvislém grafu je definována jako vzdálenost mezi tímto uzlem a uzlem jemu v grafu nejvzdálenějším.
-
Uzel s minimální excentricitou se nazývá střed grafu (obecně středů grafu může být více).
-
Poloměr souvislého grafu je definován jako excentricita jeho libovolného středu.
Úloha
Na vstupu je dán graf, je třeba určit počet jeho komponent a maximální hodnotu poloměru všech jeho komponent.
Vstup
Na vstupu jsou tři kladná celá čísla N1, N2 a D zapsaná na jednom řádku a oddělená navzájem vždy jednou mezerou.
Zkoumaný graf je určen takto:
Uzly grafu jsou všechna přirozená čísla z množiny {N1, N1+1, N1+2, …, N2}. Dva uzly a, b jsou spojeny hranou právě tehdy, když
NSD(a + b + |a − b| + 3, a × b + |a − b| + 2) ≥ D.
Platí N2 ≤ 109, 0 ≤ N2 − N1 ≤ 1000, 1 ≤ D ≤ 104.
