Dados N vértices numerados de 0 a N – 1 y E aristas para formar un gráfico no dirigido . Todos los bordes deben agregarse en el orden dado. La tarea es encontrar los bordes eliminando que no desconecten el gráfico. Si hay múltiples aristas posibles, devuelve las que ocurren más adelante en la secuencia.
Ejemplos:
Entrada: N = 3, E = 3, bordes = {{0, 1}, {1, 2}, {0, 2}}
Salida: 0 2
Explicación: Quitar cualquiera de los bordes mantiene el gráfico conectado.
Pero (0, 2) viene más tarde en la secuencia.Entrada: N = 5, E = 7, aristas = {{0, 1}, {1, 2}, {2, 3}, {4, 3}, {0, 4}, {4, 1}, { 3, 0}}
Salida:
0 4
4 1
3 0
Explicación: Después de eliminar los bordes (0, 4), (4, 1), (3, 0) el gráfico aún estará conectado. Por lo tanto, estos tres bordes son bordes adicionales.
Enfoque: este problema se puede resolver utilizando el concepto de estructura de datos de conjuntos disjuntos basado en la siguiente idea:
Siga conectando los bordes entre sí si no se han conectado previamente, si ya están conectados, entonces el borde actual seguramente será un borde adicional.
Use conjuntos disjuntos para encontrar si los Nodes estaban previamente conectados o no. Si están conectados, entonces conecta el borde y une esos dos conjuntos.
Siga los pasos a continuación para resolver el problema:
- Cree una array parent[] para almacenar los Nodes principales de cada Node.
- Cree un conjunto de pares (por ejemplo , ans ) para almacenar la respuesta.
- Ejecute un bucle a través de los bordes dados.
- Compruebe si los vértices del borde actual ya están conectados o no.
- Si están conectados, almacene este borde en el ans .
- De lo contrario, conecta estos dos vértices y une esos dos conjuntos disjuntos (es decir, haz que sus padres sean iguales).
- Regrese e imprima ans .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// The required Comparator Function.
int find(int x, vector<int>& parent)
{
if (x == parent[x]) {
return x;
}
return parent[x]
= find(parent[x], parent);
}
// Function to find extra edges
set<pair<int, int> > extraEdges(int n, int e,
vector<vector<int> >& edges)
{
set<pair<int, int> > ans;
vector<int> parent(n);
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Loop through the edges
for (auto x : edges) {
int vParent = find(x[0], parent);
int uParent = find(x[1], parent);
if (vParent == uParent) {
pair<int, int> p;
if (x[0] < x[1]) {
p = { x[0], x[1] };
}
else {
p = { x[1], x[0] };
}
ans.insert(p);
}
else {
parent[vParent] = uParent;
}
}
// Return the edges
return ans;
}
// Driver code
int main()
{
int N = 3, E = 3;
vector<vector<int> > edges
= { { 0, 1 }, { 1, 2 }, { 2, 0 }, { 0, 2 } };
set<pair<int, int> > ans = extraEdges(N,
E, edges);
for (auto& edge : ans) {
cout << edge.first << " " << edge.second << "\n";
}
return 0;
}
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// The required Comparator Function.
static int find(int x, List<int> parent)
{
if (x == parent[x]) {
return x;
}
return parent[x] = find(parent[x], parent);
}
// Function to find extra edges
static SortedSet<pair> extraEdges(int n, int e, List<List<int>> edges)
{
SortedSet<pair> ans = new SortedSet<pair>(new Comp());
List<int> parent = new List<int>();
for (int i = 0; i < n; i++) {
parent.Add(i);
}
// Loop through the edges
foreach (List<int> x in edges) {
int vParent = find(x[0], parent);
int uParent = find(x[1], parent);
if (vParent == uParent) {
pair p = new pair(0, 0);
if (x[0] < x[1]) {
p = new pair(x[0], x[1]);
}
else {
p = new pair(x[1], x[0]);
}
ans.Add(p);
}
else {
parent[vParent] = uParent;
}
}
// Return the edges
return ans;
}
// Driver Code
public static void Main(string[] args){
int N = 3, E = 3;
List<List<int>> edges = new List<List<int>>{
new List<int>{ 0, 1 },
new List<int>{ 1, 2 },
new List<int>{ 2, 0 },
new List<int>{ 0, 2 }
};
SortedSet<pair> ans = extraEdges(N, E, edges);
foreach (pair edge in ans) {
Console.WriteLine(edge.first + " " + edge.second);
}
}
}
public class pair{
public int first;
public int second;
public pair(int first,int second){
this.first = first;
this.second = second;
}
}
class Comp : IComparer<pair>{
public int Compare(pair o2,pair o1){
if(o1.first == o2.first){
return o1.second - o2.second;
}
return o1.first - o2.first;
}
}
Python3
# Python3 code to implement the above approach
def find(x,parent):
if (x == parent[x]):
return x
parent[x] = find(parent[x], parent)
return parent[x]
# Function to find extra edges
def extraEdges(n,e,edges):
ans = set()
parent = [i for i in range(n)]
# Loop through the edges
for x in edges:
vParent = find(x[0], parent)
uParent = find(x[1], parent)
if (vParent == uParent):
p = ()
if (x[0] < x[1]):
p = ( x[0], x[1] )
else:
p = ( x[1], x[0] )
ans.add(p)
else:
parent[vParent] = uParent
# Return the edges
return ans
# Driver code
N,E = 3,3
edges = [ [ 0, 1 ], [ 1, 2 ], [ 2, 0 ], [ 0, 2 ] ]
ans = extraEdges(N, E, edges)
for edge in ans:
print(f"{edge[0]} {edge[1]}")
# This code is contributed by shinjanpatra
0 2
Complejidad de tiempo: O(E * log(N))
Espacio auxiliar: O(N)