27 lines
1.3 KiB
TeX
27 lines
1.3 KiB
TeX
O grafo do sistema tem uma propriedade importante: a estação central é a única
|
|
estação com grau pelo menos $5$, pois dela saem todas as linhas radiais. As
|
|
outras estações pertencem a caminhos radiais ou à linha circular. Mesmo uma
|
|
estação onde uma radial encontra o círculo tem grau no máximo $4$.
|
|
|
|
Primeiro encontramos essa estação central analisando os graus dos vértices.
|
|
Depois removemos a central do grafo. O que resta é a linha circular com alguns
|
|
caminhos pendurados nela, correspondentes aos trechos radiais antes ou depois do
|
|
círculo.
|
|
|
|
Para isolar somente a linha circular, fazemos uma poda de folhas:
|
|
\begin{enumerate}
|
|
\item calcule o grau de cada vértice desconsiderando a estação central;
|
|
\item coloque em uma fila todos os vértices de grau $0$ ou $1$;
|
|
\item enquanto a fila não estiver vazia, remova o vértice da frente e reduza
|
|
o grau de seus vizinhos ainda não removidos;
|
|
\item quando algum vizinho passar a ter grau $1$, coloque-o na fila.
|
|
\end{enumerate}
|
|
|
|
Esse processo remove todos os caminhos que estão pendurados no ciclo. Os
|
|
vértices que não foram removidos ao final são exatamente as estações da linha
|
|
circular, então basta contá-los.
|
|
|
|
\textbf{Complexidade de tempo:} $O(N + M)$.
|
|
|
|
\textbf{Complexidade de espaço:} $O(N + M)$.
|