A continuación se muestran los pasos para encontrar MST usando el algoritmo de Kruskal 1. Clasifique todos los bordes en orden no decreciente de su peso. 2. Elija el borde más pequeño. Compruebe si forma un ciclo con el árbol de expansión formado hasta ahora. Si no se forma el ciclo, incluya este borde. De lo … Continue reading «Algoritmo de Kruskal (implementación simple para array de adyacencia)»
Considere una situación con varias personas y las siguientes tareas que deben realizarse en ellas. Agregue una nueva relación de amistad, es decir, una persona x se vuelve amiga de otra persona y. Averigüe si el individuo x es amigo del individuo y (amigo directo o indirecto) Ejemplo: We are given 10 individuals say, a, … Continue reading «Estructuras de datos de conjuntos disjuntos»
Dadas n expresiones del tipo x = y y x != y donde 1 ≤ x, y ≤ n , la tarea es verificar si los números enteros de 1 a n se pueden asignar a x e y de modo que se satisfagan todas las ecuaciones. Ejemplos: Entrada: x[] = {1, 2, 3}, op[] … Continue reading «Compruebe si las expresiones binarias dadas son válidas»
Considere una red social especial donde las personas se llaman conectadas si una persona está conectada a otra con cualquier cantidad de conexiones intermedias. Por ejemplo, si una persona x está conectada con y y y está conectada con z, entonces x también se considera conectada con z. Recibimos un conjunto de requests de amistad … Continue reading «Estructura de datos para diseñar una red social especial»
Dado un gráfico no dirigido, ¿cómo verificar si hay un ciclo en el gráfico? Ejemplo, Haga clic aquí para el curso completo! C++ // A C++ Program to detect // cycle in an undirected graph #include <iostream> #include <limits.h> #include <list> using namespace std; // Class for an undirected graph class Graph { … Continue reading «Detectar ciclo en un gráfico no dirigido»
Dado un árbol, y el costo de un subárbol se define como |S|*Y(S) donde |S| es el tamaño del subárbol y AND(S) es AND bit a bit de todos los índices de los Nodes del subárbol, la tarea es encontrar el costo máximo del posible subárbol. Requisito previo : ejemplos de unión de conjuntos disjuntos … Continue reading «Conjunto disjunto de la Unión en los árboles | conjunto 2»
La conectividad dinámica es una estructura de datos que mantiene dinámicamente la información sobre los componentes conectados del gráfico. En palabras simples, supongamos que hay un gráfico G(V, E) en el que no. de vértices V es constante pero no. de aristas E es variable. Hay tres formas en las que podemos cambiar el número … Continue reading «Conectividad Dinámica | Conjunto 1 (incremental)»
Dado un árbol y pesos de Nodes. Los pesos son enteros no negativos. La tarea es encontrar el tamaño máximo de un subárbol de un árbol dado de modo que todos los Nodes tengan pesos pares. Requisito previo: Unión de conjuntos disjuntos Ejemplos: Input : Number of nodes = 7 Weights of nodes = 1 … Continue reading «Conjunto disjunto de la Unión en los árboles | Serie 1»
Dada una array booleana 2D, encuentre el número de islas. Un grupo de unos conectados forma una isla. Por ejemplo, la siguiente array contiene 5 islas {1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, 1} Una celda en la … Continue reading «Encuentra el número de Islas | Conjunto 2 (usando conjunto disjunto)»
Dada una array binaria mat[][] de dimensiones NxM tal que 1 denota la isla y 0 denota el agua. La tarea es encontrar el número de islas cerradas en la array dada. Una isla cerrada se conoce como el grupo de 1 que está rodeado solo por 0 en los cuatro lados (excluyendo las diagonales). … Continue reading «Encuentre el número de islas cerradas en Matrix dada»