SCC's

Discussion around the algorithms: the most powerful tool of the contest programmer. This is the place to ask about the algorithms you have heard mention, or to share with the community your knowledge about them.
Forum rules
Remember that you may not post the AC solution to any of the problems on the COJ. Only code pertaining to a general algorithm will be allowed.
Posting AC solutions will be penalized.
Post Reply
HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:

SCC's

Post by HaZard » 3 years ago

Alguien puede explicarme como funciona el algoritmo, qué calcula o para qué se utiliza, Saludos


teruel

humbertodiaz
Posts: 97
Joined: 4 years ago
Gender: None specified

Re: SCC's

Post by humbertodiaz » 3 years ago

Hey Teruel.

SCC significa "strongly connected component", o en español, "componente fuertemente conexo". Es un concepto para grafos dirigidos. Intentare darte una descripcion.

Image
(Imagen de Wikipedia)

Un grafo es fuertemente conexo si existen caminos entre todos los pares de nodos en el grafo en ambas direcciones. Es decir, si tomas dos nodos arbitrarios U y V, debe existir un camino desde U hasta V y otro desde V hasta U. Si ese camino no existe para algun par de nodos, entonces el grafo no es fuertemente conexo.

Tambien se puede aplicar este concepto a los subgrafos. Un componente fuertemente conexo es un subgrafo que consiste solamente de nodos tal que cualquier par tiene caminos en ambas direcciones como en la condicion anterior. Tambien se requiere que el componente sea maximo, en el sentido que añadir cualquier nodo al subgrafo violaria la condicion de los caminos - dejaria de ser un componente fuertemente conexo.

Existen varios algoritmos para contar los CFCs de un grafo y determinar cuales nodos pertenecen a cuales componentes, todo en tiempo lineal con respecto a la cantidad de nodos y aristas: el algoritmo de Kosaraju, el algoritmo de Tarjan para componentes fuertemente conexos, y el algoritmo de componentes fuertes a base de caminos. El de Kosaraju es mas sencillo, pero a la misma vez es mas lento que los demas por que utiliza dos DFS (depth-first search), mientras que los otros dos algoritmos usan solo una busqueda.

Con respecto a las aplicaciones del algoritmo, existen varias directas e indirectas. Algunos ejercicios simplemente quieren que determines cuantos CFCs existen, el tamaño de cada componente, u otros datos relacionados. Usualmente no te lo dicen asi directamente en la descripcion, pero se puede inferir que piden algo equivalente.

Hay otros algoritmos que requieren saber los CFCs de un grafo. Uno de mis problemas algoritmicos favoritos es el problema de 2-satisfactibilidad. Es raro en competencias, pero conozco unos pocos ejercicios en COJ que se reducen a eso. Existe un algoritmo para resolver ese problema en tiempo lineal a base de representar una expresion logica como un grafo y detectar si dos terminos de la misma variable con signos opuestos estan en el mismo componente. Tambien se puede utilizar el grafo para obtener valores validos para las variables. Es un problema con aplicaciones amplias, como determinar las posiciones de componentes electronicos en un circuito, o calcular horarios para trabajos o uso de recursos.

Otra aplicacion de CFCs es formar un grafo condensado. En esencia, se representa cada componente con un nodo, y solo se incluyen conexiones entre distintos componentes. Eso forma un grafo aciclico dirigido que representa las relaciones entre componentes. Claramente debe ser aciclico, por que si existiera un ciclo entre dos componentes, se colapsarian a uno solo. Yo creo que tuve que usar ese algoritmo para determinar la minima cantidad de dominos que se debian tumbar para tumbarlos todos desde una configuracion inicial. Puedes calcular el grafo condensado y despues contar cuantos nodos en ese grafo son fuentes.

Post Reply

Return to “Algorithms”