Dado un grafo con N Nodes y M aristas. La tarea es encontrar el número de formas de seleccionar un Node de cada componente conectado del gráfico dado. Ejemplos: Aporte: Salida: 3 (1, 4), (2, 4), (3, 4) son formas posibles. Aporte: Salida: 6 (1, 4, 5), (2, 4, 5), (3, 4, 5), (1, 4, … Continue reading «Número de formas de seleccionar un Node de cada componente conectado»
Dada una array arr[] de n enteros. Para cada valor arr[i], podemos movernos a arr[i] + 1 en el sentido de las agujas del reloj considerando los elementos del arreglo en ciclo. Necesitamos contar elementos cíclicos en la array. Un elemento es cíclico si a partir de él y moviéndose a arr[i] + 1 conduce … Continue reading «Número de elementos cíclicos en una array donde podemos saltar según el valor»
Dados dos enteros positivos N y K , la tarea es construir un gráfico simple y conectado que consta de N vértices con la longitud de cada borde como 1 unidad, de modo que la distancia más corta entre exactamente K pares de vértices sea 2 . Si no es posible construir el gráfico, imprima … Continue reading «Construya un gráfico usando N vértices cuya distancia más corta entre K pares de vértices sea 2»
Un grafo dirigido es fuertemente conexo si existe un camino entre todos los pares de vértices. Un componente fuertemente conectado ( SCC ) de un gráfico dirigido es un subgrafo máximo fuertemente conectado. Por ejemplo, hay 3 SCC en el siguiente gráfico. C++ // C++ Implementation of Kosaraju’s algorithm to print all SCCs #include … Continue reading «Componentes fuertemente conectados»
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 Ejemplo: Input : mat[][] = {{1, 1, 0, 0, 0}, {0, 1, 0, 0, 1}, {1, 0, 0, 1, 1}, {0, 0, 0, 0, 0}, {1, 0, 1, 0, … Continue reading «Encuentra el número de islas | Conjunto 1 (usando DFS)»
Se da un Gráfico desconectado con N vértices y K aristas. La tarea es encontrar el recuento de subgráficos singleton. Un gráfico singleton es uno con un solo vértice. Ejemplos: Input : Vertices : 6 Edges : 1 2 1 3 5 6 Output : 1 Explanation : The Graph has 3 components : {1-2-3}, … Continue reading «Cuente los subgráficos aislados de un solo Node en un gráfico desconectado»
Dado un gráfico dirigido no ponderado, puede ser cíclico o acíclico. Imprime el número de caminos más cortos desde un vértice dado a cada uno de los vértices. Por ejemplo, considere el siguiente gráfico. Hay un camino más corto del vértice 0 al vértice 0 (desde cada vértice hay un solo camino más corto hacia … Continue reading «Número de caminos más cortos en un gráfico no ponderado y dirigido»
Un vértice en un grafo conectado no dirigido es un punto de articulación (o vértice de corte) si al eliminarlo (y los bordes a través de él) se desconecta el grafo. Los puntos de articulación representan vulnerabilidades en una red conectada: puntos únicos cuya falla dividiría la red en 2 o más componentes. Son útiles … Continue reading «Puntos de articulación (o vértices de corte) en un gráfico»
Un componente biconexo es un subgrafo biconexo maximal . El gráfico biconectado ya se trata aquí . En este artículo, veremos cómo encontrar el componente biconectado en un gráfico usando el algoritmo de John Hopcroft y Robert Tarjan. En el gráfico anterior, los siguientes son los componentes biconectados: 4–2 3–4 3–1 2–3 1–2 8–9 8–5 … Continue reading «Componentes biconectados»
¿Qué es un Vértice Madre? Un vértice madre en un grafo G = (V, E) es un vértice v tal que se puede llegar a todos los demás vértices en G por un camino desde v. Ejemplo: Input : Below Graph Output : 5 Puede haber más de un vértice madre en un gráfico. Necesitamos … Continue reading «Encuentra un vértice madre en un gráfico»