Dado un gráfico no dirigido de N Nodes etiquetados de 1 a N, la tarea es encontrar el mínimo de Nodes etiquetados que debe eliminarse del gráfico de modo que el gráfico resultante no tenga ciclo.
Nota: Si el gráfico inicial no tiene ciclo, es decir, no es necesario eliminar ningún Node, imprima -1.
Ejemplos:
Entrada: N = 5, bordes[][] = {{5, 1}, {5, 2}, {1, 2}, {2, 3}, {2, 4}}
Salida: 1
Explicación:
Si Node 1 se elimina, el gráfico resultante no tiene ciclo. De manera similar, el ciclo se puede evitar eliminando también el Node 2.
Como tenemos que encontrar el Node mínimo etiquetado, la respuesta es 1.Entrada: N = 5, bordes[][] = {{4, 5}, {4, 1}, {4, 2}, {4, 3}, {5, 1}, {5, 2}}
Salida : 4
Enfoque ingenuo: el enfoque ingenuo para este problema sería eliminar cada vértice individualmente y verificar si el gráfico resultante tiene un ciclo o no. La complejidad temporal para este enfoque es cuadrática.
Enfoque eficiente: la idea es aplicar la búsqueda primero en profundidad en el gráfico dado y observar el árbol dfs formado.
- Un Back Edge se conoce como el borde que no forma parte del árbol DFS construido y es un borde entre algún Node v y uno de los ancestros de v.
- Claramente, todos los bordes del gráfico que no forman parte del árbol DFS son bordes posteriores.
- Si no hay bordes posteriores en el gráfico, entonces el gráfico no tiene ciclo. Entonces, la respuesta será -1 en este caso.
Si hay aristas posteriores en el gráfico, entonces necesitamos encontrar la arista mínima. Para hacer esto, debemos verificar si el ciclo se elimina al eliminar un borde específico del gráfico. Por lo tanto, sea v un vértice que estamos comprobando actualmente. Por lo tanto, las siguientes condiciones deben ser seguidas por el vértice v de tal manera que al quitarlo, no daría lugar a ningún ciclo:
- v debe estar en la ruta del árbol que conecta los puntos finales de cada borde posterior del gráfico.
Prueba: suponga que existe algún borde posterior xy, tal que v no se encuentra en la ruta del árbol. Si eliminamos v, aún podríamos atravesar de x a y, y volver a x a través del borde posterior, lo que indica que el ciclo no se elimina. - El subárbol de v debe tener como máximo una arista posterior a cualquier ancestro de v.
Prueba: Sea el subárbol S que tenga aristas posteriores wx e yz tales que w e y están en S y x y z son ancestros de v. Si elimine v, claramente todavía existe un ciclo que consiste en el camino entre w y y, el camino de xa z y los dos bordes traseros wx e yz, es decir, el ciclo no se elimina.
Por lo tanto, la idea es mantener un registro de los bordes posteriores y un indicador del número de bordes posteriores en el subárbol de un Node para cualquiera de sus ancestros. Para realizar un seguimiento de los bordes posteriores, utilizaremos un algoritmo de coloreado de gráficos DFS modificado .
Para verificar si el subárbol v tiene como máximo un borde posterior a cualquier ancestro de v o no, implementamos dfs de modo que devuelva la profundidad de los dos bordes más altos del subárbol de v. Mantenemos una array donde cada índice ‘ i’ en el arreglo almacena si la condición 2 de arriba es satisfecha por el Node ‘i’ o no. De manera similar, se implementan dos arreglos, uno para el hijo y otro para el padre para ver si el Node v se encuentra en la ruta del árbol que conecta los puntos finales.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the
// minimum labelled node to be
// removed such that there is no
// cycle in the undirected graph
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100005;
int totBackEdges;
int countAdj[MAX], small[MAX];
// Variables to store if a node V has
// at-most one back edge and store the
// depth of the node for the edge
int isPossible[MAX], depth[MAX];
vector<int> adj[MAX];
int vis[MAX];
// Function to swap the pairs of the graph
void change(pair<int, int>& p, int x)
{
// If the second value is
// greater than x
if (p.second > x)
p.second = x;
// Put the pair in the ascending
// order internally
if (p.first > p.second)
swap(p.first, p.second);
}
// Function to perform the DFS
pair<int, int> dfs(int v, int p = -1, int de = 0)
{
// Initialise with the large value
pair<int, int> answer(100000000, 100000000);
// Storing the depth of this vertex
depth[v] = de;
// Mark the vertex as visited
vis[v] = 1;
isPossible[v] = 1;
// Iterating through the graph
for (int u : adj[v]) {
// If the node is a child node
if (u ^ p) {
// If the child node is unvisited
if (!vis[u]) {
// Move to the child and increase
// the depth
auto x = dfs(u, v, de + 1);
// increase according to algorithm
small[v] += small[u];
change(answer, x.second);
change(answer, x.first);
// If the node is not having
// exactly K backedges
if (x.second < de)
isPossible[v] = 0;
}
// If the child is already visited
// and in current dfs
// (because colour is 1)
// then this is a back edge
else if (vis[u] == 1) {
totBackEdges++;
// Increase the countAdj values
countAdj[v]++;
countAdj[u]++;
small[p]++;
small[u]--;
change(answer, depth[u]);
}
}
}
// Colour this vertex 2 as
// we are exiting out of
// dfs for this node
vis[v] = 2;
return answer;
}
// Function to find the minimum labelled
// node to be removed such that
// there is no cycle in the undirected graph
int minNodetoRemove(
int n,
vector<pair<int, int> > edges)
{
// Construct the graph
for (int i = 0; i < edges.size(); i++) {
adj[edges[i].first]
.push_back(edges[i].second);
adj[edges[i].second]
.push_back(edges[i].first);
}
// Mark visited as false for each node
memset(vis, 0, sizeof(vis));
totBackEdges = 0;
// Apply dfs on all unmarked nodes
for (int v = 1; v <= n; v++) {
if (!vis[v])
dfs(v);
}
// If no backedges in the initial graph
// this means that there is no cycle
// So, return -1
if (totBackEdges == 0)
return -1;
int node = -1;
// Iterate through the vertices and
// return the first node that
// satisfies the condition
for (int v = 1; v <= n; v++) {
// Check whether the count sum of
// small[v] and count is the same as
// the total back edges and
// if the vertex v can be removed
if (countAdj[v] + small[v]
== totBackEdges
&& isPossible[v]) {
node = v;
}
if (node != -1)
break;
}
return node;
}
// Driver code
int main()
{
int N = 5;
vector<pair<int, int> > edges;
edges.push_back(make_pair(5, 1));
edges.push_back(make_pair(5, 2));
edges.push_back(make_pair(1, 2));
edges.push_back(make_pair(2, 3));
edges.push_back(make_pair(2, 4));
cout << minNodetoRemove(N, edges);
}
Java
// Java implementation to find the
// minimum labelled node to be
// removed such that there is no
// cycle in the undirected graph
import java.util.ArrayList;
import java.util.Arrays;
class Pair
{
int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
class GFG{
static final int MAX = 100005;
static int totBackEdges;
static int[] countAdj = new int[MAX];
static int[] small = new int[MAX];
// Variables to store if a node V has
// at-most one back edge and store the
// depth of the node for the edge
static int[] isPossible = new int[MAX];
static int[] depth = new int[MAX];
@SuppressWarnings("unchecked")
static ArrayList<Integer>[] adj = new ArrayList[MAX];
static int[] vis = new int[MAX];
// Function to swap the pairs of the graph
static void change(Pair p, int x)
{
// If the second value is
// greater than x
if (p.second > x)
p.second = x;
// Put the Pair in the ascending
// order internally
if (p.first > p.second)
{
int tmp = p.first;
p.first = p.second;
p.second = tmp;
}
}
// Function to perform the DFS
static Pair dfs(int v, int p, int de)
{
// Initialise with the large value
Pair answer = new Pair(100000000, 100000000);
// Storing the depth of this vertex
depth[v] = de;
// Mark the vertex as visited
vis[v] = 1;
isPossible[v] = 1;
// Iterating through the graph
for(int u : adj[v])
{
// If the node is a child node
if ((u ^ p) != 0)
{
// If the child node is unvisited
if (vis[u] == 0)
{
// Move to the child and increase
// the depth
Pair x = dfs(u, v, de + 1);
// increase according to algorithm
small[v] += small[u];
change(answer, x.second);
change(answer, x.first);
// If the node is not having
// exactly K backedges
if (x.second < de)
isPossible[v] = 0;
}
// If the child is already visited
// and in current dfs
// (because colour is 1)
// then this is a back edge
else if (vis[u] == 1)
{
totBackEdges++;
// Increase the countAdj values
countAdj[v]++;
countAdj[u]++;
small[p]++;
small[u]--;
change(answer, depth[u]);
}
}
}
// Colour this vertex 2 as
// we are exiting out of
// dfs for this node
vis[v] = 2;
return answer;
}
// Function to find the minimum labelled
// node to be removed such that
// there is no cycle in the undirected graph
static int minNodetoRemove(int n, ArrayList<Pair> edges)
{
// Construct the graph
for(int i = 0; i < edges.size(); i++)
{
adj[edges.get(i).first].add(
edges.get(i).second);
adj[edges.get(i).second].add(
edges.get(i).first);
}
// Mark visited as false for each node
Arrays.fill(vis, 0);
totBackEdges = 0;
// Apply dfs on all unmarked nodes
for(int v = 1; v <= n; v++)
{
if (vis[v] == 0)
dfs(v, -1, 0);
}
// If no backedges in the initial graph
// this means that there is no cycle
// So, return -1
if (totBackEdges == 0)
return -1;
int node = -1;
// Iterate through the vertices and
// return the first node that
// satisfies the condition
for(int v = 1; v <= n; v++)
{
// Check whether the count sum of
// small[v] and count is the same as
// the total back edges and
// if the vertex v can be removed
if ((countAdj[v] + small[v] == totBackEdges) &&
isPossible[v] != 0)
{
node = v;
}
if (node != -1)
break;
}
return node;
}
// Driver code
public static void main(String[] args)
{
int N = 5;
ArrayList<Pair> edges = new ArrayList<>();
for(int i = 0; i < MAX; i++)
{
adj[i] = new ArrayList<>();
}
edges.add(new Pair(5, 1));
edges.add(new Pair(5, 2));
edges.add(new Pair(1, 2));
edges.add(new Pair(2, 3));
edges.add(new Pair(2, 4));
System.out.println(minNodetoRemove(N, edges));
}
}
// This code is contributed by sanjeev2552
Python3
# Python3 implementation to find the # minimum labelled node to be # removed such that there is no # cycle in the undirected graph MAX = 100005; totBackEdges = 0 countAdj = [0 for i in range(MAX)] small = [0 for i in range(MAX)] # Variables to store if a node V has # at-most one back edge and store the # depth of the node for the edge isPossible = [0 for i in range(MAX)] depth = [0 for i in range(MAX)] adj = [[] for i in range(MAX)] vis = [0 for i in range(MAX)] # Function to swap the pairs of the graph def change(p, x): # If the second value is # greater than x if (p[1] > x): p[1] = x; # Put the pair in the ascending # order internally if (p[0] > p[1]): tmp = p[0]; p[0] = p[1]; p[1] = tmp; # Function to perform the DFS def dfs(v, p = -1, de = 0): global vis, totBackEdges # Initialise with the large value answer = [100000000, 100000000] # Storing the depth of this vertex depth[v] = de; # Mark the vertex as visited vis[v] = 1; isPossible[v] = 1; # Iterating through the graph for u in adj[v]: # If the node is a child node if ((u ^ p) != 0): # If the child node is unvisited if (vis[u] == 0): # Move to the child and increase # the depth x = dfs(u, v, de + 1); # increase according to algorithm small[v] += small[u]; change(answer, x[1]); change(answer, x[0]); # If the node is not having # exactly K backedges if (x[1] < de): isPossible[v] = 0; # If the child is already visited # and in current dfs # (because colour is 1) # then this is a back edge elif (vis[u] == 1): totBackEdges += 1 # Increase the countAdj values countAdj[v] += 1 countAdj[u] += 1 small[p] += 1 small[u] -= 1 change(answer, depth[u]); # Colour this vertex 2 as # we are exiting out of # dfs for this node vis[v] = 2; return answer; # Function to find the minimum labelled # node to be removed such that # there is no cycle in the undirected graph def minNodetoRemove( n, edges): # Construct the graph for i in range(len(edges)): adj[edges[i][0]].append(edges[i][1]); adj[edges[i][1]].append(edges[i][0]); global vis, totBackEdges # Mark visited as false for each node vis = [0 for i in range(len(vis))] totBackEdges = 0; # Apply dfs on all unmarked nodes for v in range(1, n + 1): if (vis[v] == 0): dfs(v); # If no backedges in the initial graph # this means that there is no cycle # So, return -1 if (totBackEdges == 0): return -1; node = -1; # Iterate through the vertices and # return the first node that # satisfies the condition for v in range(1, n + 1): # Check whether the count sum of # small[v] and count is the same as # the total back edges and # if the vertex v can be removed if ((countAdj[v] + small[v] == totBackEdges) and isPossible[v] != 0): node = v; if (node != -1): break; return node; # Driver code if __name__=='__main__': N = 5; edges = [] edges.append([5, 1]); edges.append([5, 2]); edges.append([1, 2]); edges.append([2, 3]); edges.append([2, 4]); print(minNodetoRemove(N, edges)); # This code is contributed by Pratham76
C#
// C# implementation to find the
// minimum labelled node to be
// removed such that there is no
// cycle in the undirected graph
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
static int MAX = 100005;
static int totBackEdges;
static int []countAdj = new int[MAX];
static int []small = new int[MAX];
// Variables to store if a node V has
// at-most one back edge and store the
// depth of the node for the edge
static int []isPossible = new int[MAX];
static int []depth = new int[MAX];
static ArrayList adj = new ArrayList();
static int []vis = new int[MAX];
class pair
{
public int first, second;
public pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to swap the pairs of the graph
static void change(ref pair p, int x)
{
// If the second value is
// greater than x
if (p.second > x)
p.second = x;
// Put the pair in the ascending
// order internally
if (p.first > p.second)
{
int tmp = p.first;
p.first = p.second;
p.second = tmp;
}
}
// Function to perform the DFS
static pair dfs(int v, int p = -1, int de = 0)
{
// Initialise with the large value
pair answer = new pair(100000000, 100000000);
// Storing the depth of this vertex
depth[v] = de;
// Mark the vertex as visited
vis[v] = 1;
isPossible[v] = 1;
// Iterating through the graph
foreach (int u in (ArrayList)adj[v]) {
// If the node is a child node
if ((u ^ p) != 0) {
// If the child node is unvisited
if (vis[u] == 0) {
// Move to the child and increase
// the depth
pair x = dfs(u, v, de + 1);
// increase according to algorithm
small[v] += small[u];
change(ref answer, x.second);
change(ref answer, x.first);
// If the node is not having
// exactly K backedges
if (x.second < de)
isPossible[v] = 0;
}
// If the child is already visited
// and in current dfs
// (because colour is 1)
// then this is a back edge
else if (vis[u] == 1) {
totBackEdges++;
// Increase the countAdj values
countAdj[v]++;
countAdj[u]++;
small[p]++;
small[u]--;
change(ref answer, depth[u]);
}
}
}
// Colour this vertex 2 as
// we are exiting out of
// dfs for this node
vis[v] = 2;
return answer;
}
// Function to find the minimum labelled
// node to be removed such that
// there is no cycle in the undirected graph
static int minNodetoRemove(
int n,
ArrayList edges)
{
// Construct the graph
for (int i = 0; i < edges.Count; i++) {
((ArrayList)adj[((pair)edges[i]).first])
.Add(((pair)edges[i]).second);
((ArrayList)adj[((pair)edges[i]).second])
.Add(((pair)edges[i]).first);
}
// Mark visited as false for each node
Array.Fill(vis, 0);
totBackEdges = 0;
// Apply dfs on all unmarked nodes
for (int v = 1; v <= n; v++) {
if (vis[v] == 0)
dfs(v);
}
// If no backedges in the initial graph
// this means that there is no cycle
// So, return -1
if (totBackEdges == 0)
return -1;
int node = -1;
// Iterate through the vertices and
// return the first node that
// satisfies the condition
for (int v = 1; v <= n; v++) {
// Check whether the count sum of
// small[v] and count is the same as
// the total back edges and
// if the vertex v can be removed
if ((countAdj[v] + small[v] == totBackEdges) && isPossible[v] != 0) {
node = v;
}
if (node != -1)
break;
}
return node;
}
// Driver code
static void Main()
{
int N = 5;
ArrayList edges = new ArrayList();
for(int i = 0; i < MAX; i++)
{
adj.Add(new ArrayList());
}
edges.Add(new pair(5, 1));
edges.Add(new pair(5, 2));
edges.Add(new pair(1, 2));
edges.Add(new pair(2, 3));
edges.Add(new pair(2, 4));
Console.Write(minNodetoRemove(N, edges));
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript implementation to find the
// minimum labelled node to be
// removed such that there is no
// cycle in the undirected graph
var MAX = 100005;
var totBackEdges;
var countAdj = Array(MAX).fill(0);
var small = Array(MAX).fill(0);
// Variables to store if a node V has
// at-most one back edge and store the
// depth of the node for the edge
var isPossible = Array(MAX).fill(0);
var depth = Array(MAX).fill(0);
var adj = [];
var vis = Array(MAX).fill(0);
class pair
{
constructor(first, second)
{
this.first = first;
this.second = second;
}
}
// Function to swap the pairs of the graph
function change(p, x)
{
// If the second value is
// greater than x
if (p.second > x)
p.second = x;
// Put the pair in the ascending
// order internally
if (p.first > p.second)
{
var tmp = p.first;
p.first = p.second;
p.second = tmp;
}
}
// Function to perform the DFS
function dfs(v, p = -1, de = 0)
{
// Initialise with the large value
var answer = new pair(100000000, 100000000);
// Storing the depth of this vertex
depth[v] = de;
// Mark the vertex as visited
vis[v] = 1;
isPossible[v] = 1;
// Iterating through the graph
for(var u of adj[v])
{
// If the node is a child node
if ((u ^ p) != 0)
{
// If the child node is unvisited
if (vis[u] == 0)
{
// Move to the child and increase
// the depth
var x = dfs(u, v, de + 1);
// Increase according to algorithm
small[v] += small[u];
change(answer, x.second);
change(answer, x.first);
// If the node is not having
// exactly K backedges
if (x.second < de)
isPossible[v] = 0;
}
// If the child is already visited
// and in current dfs
// (because colour is 1)
// then this is a back edge
else if (vis[u] == 1)
{
totBackEdges++;
// Increase the countAdj values
countAdj[v]++;
countAdj[u]++;
small[p]++;
small[u]--;
change(answer, depth[u]);
}
}
}
// Colour this vertex 2 as
// we are exiting out of
// dfs for this node
vis[v] = 2;
return answer;
}
// Function to find the minimum labelled
// node to be removed such that
// there is no cycle in the undirected graph
function minNodetoRemove(n, edges)
{
// Construct the graph
for(var i = 0; i < edges.length; i++)
{
(adj[(edges[i]).first]).push(
(edges[i]).second);
(adj[(edges[i]).second]).push(
(edges[i]).first);
}
// Mark visited as false for each node
vis = Array(MAX).fill(0);
totBackEdges = 0;
// Apply dfs on all unmarked nodes
for(var v = 1; v <= n; v++)
{
if (vis[v] == 0)
dfs(v);
}
// If no backedges in the initial graph
// this means that there is no cycle
// So, return -1
if (totBackEdges == 0)
return -1;
var node = -1;
// Iterate through the vertices and
// return the first node that
// satisfies the condition
for(var v = 1; v <= n; v++)
{
// Check whether the count sum of
// small[v] and count is the same as
// the total back edges and
// if the vertex v can be removed
if ((countAdj[v] + small[v] == totBackEdges) &&
isPossible[v] != 0)
{
node = v;
}
if (node != -1)
break;
}
return node;
}
// Driver code
var N = 5;
var edges = [];
for(var i = 0; i < MAX; i++)
{
adj.push(new Array());
}
edges.push(new pair(5, 1));
edges.push(new pair(5, 2));
edges.push(new pair(1, 2));
edges.push(new pair(2, 3));
edges.push(new pair(2, 4));
document.write(minNodetoRemove(N, edges));
// This code is contributed by rrrtnx
</script>
Producción:
1
Complejidad de tiempo: O(N + M) , donde N es el número de Nodes y M es el número de aristas.
Espacio Auxiliar: O(N + M).