Programa en C para conjunto disjunto (o búsqueda de unión) | Conjunto 1 (Detectar ciclo en un gráfico no dirigido)

Una estructura de datos de conjunto disjunto es una estructura de datos que realiza un seguimiento de un conjunto de elementos divididos en varios subconjuntos disjuntos (que no se superponen). Un algoritmo de búsqueda de unión es un algoritmo que realiza dos operaciones útiles en una estructura de datos de este tipo:

Buscar: determina en qué subconjunto se encuentra un elemento en particular. Esto se puede usar para determinar si dos elementos están en el mismo subconjunto.

Unión: unir dos subconjuntos en un solo subconjunto.

En esta publicación, discutiremos la aplicación de la estructura de datos de conjuntos disjuntos. La aplicación es para comprobar si un gráfico dado contiene un ciclo o no.

El algoritmo Union-Find se puede usar para verificar si un gráfico no dirigido contiene un ciclo o no. Tenga en cuenta que hemos discutido un algoritmo para detectar el ciclo . Este es otro método basado en Union-Find . Este método asume que el gráfico no contiene bucles automáticos.
Podemos realizar un seguimiento de los subconjuntos en una array 1D, llamémoslo parent[].

Consideremos el siguiente gráfico:

Para cada arista, haz subconjuntos usando ambos vértices de la arista. Si ambos vértices están en el mismo subconjunto, se encuentra un ciclo.

Inicialmente, todas las ranuras de la array principal se inicializan en -1 (significa que solo hay un elemento en cada subconjunto).

0   1   2
-1 -1  -1 

Ahora procese todos los bordes uno por uno.

Arista 0-1: Encuentra los subconjuntos en los que están los vértices 0 y 1. Como están en diferentes subconjuntos, tomamos la unión de ellos. Para tomar la unión, haga que el Node 0 sea padre del Node 1 o viceversa.

0   1   2    <----- 1 is made parent of 0 (1 is now representative of subset {0, 1})
1  -1  -1

Edge 1-2: 1 está en el subconjunto 1 y 2 está en el subconjunto 2. Entonces, tome la unión.

0   1   2    <----- 2 is made parent of 1 (2 is now representative of subset {0, 1, 2})
1   2  -1

Edge 0-2: 0 está en el subconjunto 2 y 2 también está en el subconjunto 2. Por lo tanto, incluir este borde forma un ciclo.

¿Cómo el subconjunto de 0 es igual a 2?
0->1->2 // 1 es padre de 0 y 2 es padre de 1