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":
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:
|
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com