PKU 2793 - Cactus

Autor da análise: schultzschultz

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2793

Resumo

Um grafo não direcionado $G = (V, E)$ é dito um cacto se não há uma aresta $\{u, v\}\in E$ que faz parte de dois ou mais ciclos de $G$.

A "cactualidade" de um cacto $G$ é o número de subconjuntos $E'\subseteq E$ tais que $G'= (V, E')$ ainda é um cacto. Denotaremos esses subconjuntos por subcactos. Note que, em particular, a cactualidade de uma árvore é 1. Ainda, definimos a cactualidade de um grafo que não é um cacto como 0.

Dado um grafo $G = (V,E)$ descrito por seu número de vértices e um conjunto de caminhos que não têm arestas em comum e percorrem todas as arestas de $G$, calcule a cactualidade de $G$.

Solução

Vamos inicialmente desenvolver um algoritmo para calcular a cactualidade de um grafo que sabemos ser um cacto. Depois vamos adaptá-lo para também decidir se o grafo que recebemos é ou não um cacto.

Caracterização das Pontes de um Cacto $G$

Se $C_0,\cdots,C_{k-1}$ são os ciclos de um cacto $G$ representados como conjuntos de arestas, então o conjunto das pontes de $G$, i.e., o conjunto das arestas de $G$ cuja remoção desconectaria o grafo, é

(1)
\begin{align} P = E\setminus \bigcup_{j=0}^{k-1} C_j. \end{align}

Para provar isso, basta mostrar que cada aresta em $P$ é de fato uma ponte, pois as arestas em $E\setminus P$ com certeza não o são, visto que integram um ciclo.

Se uma aresta $\{u, v\}\in P$ for removida e mesmo assim $G$ continuar conexo, existirá um caminho $\rho = \left\{\{u, v_1\},\{v_1,v_2\},\cdots,\{v_{q-1}, v\}\right\}$ em $G\setminus\{u, v\}$. Logo $\rho' = \rho\cup \{u, v\}$ é um ciclo em $G$ diferente de qualquer um dos $C_j$, pois $\{u, v\}\in P$. Se $\rho\cap (E\setminus P) = \{\}$, então na verdade $\rho'$ era um ciclo do cacto que não foi contabilizado na lista $C_0,\cdots,C_{k-1}$, um absurdo. Por outro lado, se $\exists e\in \rho\cap (E\setminus P)$, então $e\in E$ é uma aresta que pertence a algum $C_j$ e ao mesmo tempo a $\rho'$, donde $G$ não é um cacto, um absurdo. Logo $P$ realmente é o conjunto das pontes de $G$.

Caracterização dos Subcactos e da Cactualidade de um Cacto $G$

Da discussão acima, qualquer subcacto de $G$ deve incluir $P$, pois do contrário o grafo ficaria desconexo, já que provamos que $P$ é o conjunto das pontes de $G$.

Quanto a $E\setminus P$, caso sejam removidas as arestas $\{u,v\},\{u', v'\}\in C_j$ de um mesmo ciclo de $G$ e $G$ continue conexo, vai haver um caminho $\rho$ conectando $u$ e $v$ com ao menos uma aresta $\{a, b\}$ fora do ciclo $C_j$, pois este não mais é conexo. Logo o ciclo $[u\leadsto a, b, b\leadsto v, u]$ contém uma aresta de $C_j$ e uma aresta externa a $C_j$, e assim a aresta $\{u, v\}$ pertence a dois ciclos distintos, e assim $G$ não é um cacto, contradição. Portanto um subcacto de $G$ deve remover de $G$ não mais que uma aresta por ciclo.

Ainda, se $S\subseteq S' \subseteq E$ e $S$ é um subcacto de $G$, então $S'$ também o é, pois a conexidade de $S$ implica na de $S'$ e a ausência de arestas em mais de um ciclo de $E$ implica na de $S'$.

Portanto, provamos que um subconjunto $S\in E$ é subcacto de $G$ se, e somente se, $E\setminus S$ não contém arestas de $P$ e contém no máximo 1 aresta em $C_j$, 0\le j < k$.

Portanto, a cactualidade de $G$ é

(2)
\begin{align} \prod_{j=0}^{k-1} 1+\left|C_j\right|. \end{align}

Algoritmo para Computar a Cactualidade de um Cacto $G$

Agora vamos ao algoritmo. Temos que calcular $|C_j|$ para cada $j$. Fazemos uma DFS de qualquer vértice. Para cada ciclo $C_j$ no grafo, seja $u$ o primeiro vértice a ser descoberto no ciclo e $v$ e $v'$ os vértices adjacentes a $u$ em $C_j$. Na árvore de DFS, $v$ e $v'$ serão descendentes de $u$, pois $u$ foi o primeiro vértice do ciclo a ser atingido e há caminho dele para esses dois vértices. Sem perda de generalidade, assumimos que $v'$ é descoberto antes de $v$ na DFS, e nesse caso $v$ irá gerar uma back-edge com $u$. Aí nosso algoritmo computa a distância $d$ de $u$ a $v$ na árvore de DFS. Como não existe mais de um caminho de $u$ até $v$ que não use a aresta $\{u, v\}$ (pois $G$ é um cacto), o caminho de $u$ até $v$ na árvore de DFS (mais a aresta $\{v, u\}$) corresponde ao ciclo $C_j$, e portanto $|C_j| = 1+d$.

Algoritmo para Decidir se um Grafo é um Cacto

Agora só falta adaptar o algoritmo para decidir se $G$ é um cacto. Para isso adicionamos ao algoritmo anterior um conjunto $X$ dos vértices $u$ tais que o algoritmo já determinou que $\{u,\pi_u\}$ é uma aresta de um ciclo no cacto, onde $\pi_u$ é o pai de $u$ na árvore de DFS.

Como o grafo é não-direcionado, não existem cross-edges na DFS, então só nos preocuparemos com tree-edges e back-edges.

Ao encontrar uma back-edge, inserimos os vértices do ciclo (a menos do primeiro, $u$) no conjunto $X$, de forma a estabelecer que as arestas do ciclo estão marcadas (a menos da última, a back-edge). Se este ciclo descoberto partilhar uma aresta com algum outro ciclo, irá existir um vértice $w$ na "pilha" da DFS que está mais no topo tal que existe um ciclo atingível a partir de $w$ que partilhe uma aresta com o ciclo recém descoberto. Note que $w$ não pode ser $u$ e consequentemente agora $w\in X$. Quando seguirmos a DFS a partir de $w$, necessariamente a back-edge que ela vai gerar ao tocar novamente nosso ciclo terminará num ascendente de $w$. Isso ocorre porque como ela é uma back-edge ou ela termina num descendente ou num ascendente de $w$. Se ela terminasse num descendente próprio $v$ de $w$, $v$ teria contato com esse ciclo e isso contradiria nossa escolha de $w$. Como ela termina num ascendente de $w$, quando o caminho for retrocedido ele irá passar por $w$, que estará marcado (em $X$), e aí o algoritmo terá condições de rejeitar o grafo.

Note que mesmo que a única aresta comum entre os ciclos seja a back-edge, que não está marcada, esse argumento vale, pois a back-edge gerada pelo segundo ciclo irá terminar em $u$, que é um ascendente de $w$.

Até aqui, nosso algoritmo foi capaz de determinar se o grafo é ou não um cacto e, em caso positivo, dar uma lista com as cardinalidades dos ciclos $C_0,\cdots, C_{k-1}$ de $G$. Como ele é nada mais que uma DFS comum e cada ciclo é retrocedido no máximo uma vez (cada aresta é marcada no máximo uma vez na árvore), a complexidade até aqui é $\mathcal O(|V|+|E|)$.

Bignums…

Então, no final teremos ciclos $C_0,\cdots,C_{k-1}$ no grafo e teremos que computar o produto

(3)
\begin{align} \prod_{j=0}^{k-1}1+|C_j|. \end{align}

Já adianto que esse número pode ser maior ou igual a $2^{64}$ e então bignums se farão necessários.

Há basicamente duas maneiras de fazer isso. A primerira, a mais simples de implementar, é computar iterativamente os produtos, dando um algoritmo $\mathcal O\left(k^2\right)$. O problema é que podemos fazer $k\in\Theta(n)$ no pior caso, então o algoritmo fica $\mathcal O\left(n^2\right)$. Felizmente, a constante é pequena e o algoritmo passa.

Outra forma seria fazer um algoritmo dividir-e-conquistar, que teria uma complexidade bem menor, mas isso faria necessária a implementação de uma rotina de multiplicação de inteiros não igênua, o que pode ser complexo, então realmente não vale a pena aqui.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License