Runda 3: Kaktus (rozwiązanie)

01.12.2009

Autor zadania: Przemysław Pietrzkiewicz

Grafy będące przedmiotem zadania faktycznie nazywa się kaktusami. Problemy związane z tą klasą grafów kilkukrotnie pojawiały się na rosyjskich eliminacjach do konkursu ACM ICPC. Postawiony w zadaniu problem można było rozwiązać na conajmniej trzy sposoby.

Pierwsze, bardzo łatwe do zastosowania rozwiązanie bazuje na pojęciu dwuspójnej składowej. Po obliczeniu dla każdej krawędzi numeru dwuspójnej składowej, do której należy, wystarczy zauważyć, że w kaktusie każda dwuspójna musi być albo cyklem, albo pojedynczą krawędzią. Dowód "w dwie strony":

  • Każda dwuspójna jest cyklem albo pojedynczą krawędzią => w grafie nie ma dwóch cykli prostych o wspólnej krawędzi (bo wtedy dwuspójna zawierające te dwa cykle byłaby bardziej skomplikowana), czyli graf jest kaktusem.
  • Graf jest kaktusem => każdy jego cykl prosty stanowi jedną dwuspójną składową, każda krawędź nie należąca do cyklu także => każda dwuspójna jest albo cyklem prostym, albo pojedynczą krawędzią.

Sprawdzenie tego warunku nie jest trudne a otrzymane rozwiązanie ma złożoność liniową.

Inne rozwiązania, których nie będziemy szerzej omawiać to:

  • Ściągnięcie cykli prostych do pojedynczych wierzchołków (rozwiązanie wzorcowe)
  • Odpowiednio zaprojektowany DFS (do poprawności wielu rozwiązań opartych na tej metodzie trudno się przekonać na pierwszy rzut oka, łatwo też o błąd. Osobiście więc - nie polecam )

Organizatorzy:

Wrocławski Portal Informatyczny Instytut Informatyki Uniwersytet Wrocławski Wrocław

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com