|
Given an undirected tree of N vertices and N-1 edges. But now a friend has added an extra edge to the tree. You have to find an edge that your friend could have added. If there are multiple such possible edges then Print any.
Examples:
Input: N = 3, edges:[[1 2], [1 3], [2 3]]
Output: [2 3]
Explanation: We can remove any one of the three edges to get a valid tree.
Input: N=5 edges = [[1,2], [2,3], [3,4], [1,4], [1,5]]
Output: [1, 4]
Explanation: If we remove the edge [1, 5], the tree structure will be lost, and we will have two disconnected components (subtrees). Any edge apart from [1, 5] can be removed to get a valid tree.
Approach: To solve the problem follow the below idea:
The approach used in this code is Union-Find, also known as Disjoint Set Union (DSU). We will store the root parent of a node as well as the size of the subtree in one array parent[].
- If parent[i] is positive, then it means that parent[i] is the parent of node i
- If parent[i] is negative, then it means that the current node is the root parent of its set and the size of the set is the absolute value of parent[i].
Follow the steps mentioned below to implement the idea:
- Initially, we have N nodes represented by integers from 1 to N.
- Initialize an array parent[] with all values as -1, denoting that this node is the root parent of this set.
- Since no nodes are connected in the beginning, each node is the root parent of its set.
- For each edge in the input graph, we perform the following steps:
- Find the root parent (ultimate parent) of each node using the find function. This is done recursively until we find the root parent of a node.
- If the root parents of both nodes of the edges are the same, it means adding this edge would create a cycle in the graph, making it redundant. In this case, we return this edge.
- If the root parents are different, we union the two nodes by size. We attach the smaller set to the larger set to maintain balance and update the size accordingly.
- If we have processed all edges without finding a redundant one, we return {-1, -1} to indicate that no redundant connection exists.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
int find(int node, vector<int>& parent)
{
if (parent[node] < 0)
return node;
return parent[node] = find(parent[node], parent);
}
void unionBySize(int par_u, int par_v, vector<int>& parent)
{
if (parent[par_u] < parent[par_v]) {
parent[par_u] += parent[par_v];
parent[par_v] = par_u;
}
else {
parent[par_v] += parent[par_u];
parent[par_u] = par_v;
}
}
vector<int>
findRedundantConnection(vector<vector<int> >& edges,
vector<int>& parent)
{
for (auto& edge : edges) {
int u = edge[0], v = edge[1];
int par_u = find(u, parent);
int par_v = find(v, parent);
if (par_u == par_v)
return { u, v };
unionBySize(par_u, par_v, parent);
}
return { -1, -1 };
}
int main()
{
int N = 3;
vector<vector<int> > edges
= { { 1, 2 }, { 1, 3 }, { 2, 3 } };
vector<int> parent(N + 1, -1);
vector<int> redundant
= findRedundantConnection(edges, parent);
if (redundant[0] == -1) {
cout << "Not found" << endl;
}
else {
cout << redundant[0] << " " << redundant[1] << endl;
}
return 0;
}
|
Java
import java.util.*;
class Main {
static int find(int node, int[] parent) {
if (parent[node] < 0)
return node;
return parent[node] = find(parent[node], parent);
}
static void unionBySize(int par_u, int par_v, int[] parent) {
if (parent[par_u] < parent[par_v]) {
parent[par_u] += parent[par_v];
parent[par_v] = par_u;
}
else {
parent[par_v] += parent[par_u];
parent[par_u] = par_v;
}
}
static int[] findRedundantConnection(int[][] edges, int[] parent) {
for (int[] edge : edges) {
int u = edge[0], v = edge[1];
int par_u = find(u, parent);
int par_v = find(v, parent);
if (par_u == par_v)
return new int[] { u, v };
unionBySize(par_u, par_v, parent);
}
return new int[] { -1, -1 };
}
public static void main(String[] args) {
int N = 3;
int[][] edges = { { 1, 2 }, { 1, 3 }, { 2, 3 } };
int[] parent = new int[N + 1];
Arrays.fill(parent, -1);
int[] redundant = findRedundantConnection(edges, parent);
if (redundant[0] == -1) {
System.out.println("Not found");
} else {
System.out.println(redundant[0] + " " + redundant[1]);
}
}
}
|
Python3
def find(node, parent):
if parent[node] < 0:
return node
parent[node] = find(parent[node], parent)
return parent[node]
def unionBySize(par_u, par_v, parent):
if parent[par_u] < parent[par_v]:
parent[par_u] += parent[par_v]
parent[par_v] = par_u
else:
parent[par_v] += parent[par_u]
parent[par_u] = par_v
def findRedundantConnection(edges, parent):
for edge in edges:
u, v = edge
par_u = find(u, parent)
par_v = find(v, parent)
if par_u == par_v:
return [u, v]
unionBySize(par_u, par_v, parent)
return [-1, -1]
N = 3
edges = [[1, 2], [1, 3], [2, 3]]
parent = [-1] * (N + 1)
redundant = findRedundantConnection(edges, parent)
if redundant[0] == -1:
print("Not found")
else:
print(redundant[0], redundant[1])
|
C#
using System;
class GFG {
static int Find(int node, int[] parent) {
if (parent[node] < 0)
return node;
return parent[node] = Find(parent[node], parent);
}
static void UnionBySize(int par_u, int par_v, int[] parent) {
if (parent[par_u] < parent[par_v]) {
parent[par_u] += parent[par_v];
parent[par_v] = par_u;
}
else {
parent[par_v] += parent[par_u];
parent[par_u] = par_v;
}
}
static int[] FindRedundantConnection(int[][] edges, int[] parent) {
foreach (int[] edge in edges) {
int u = edge[0], v = edge[1];
int par_u = Find(u, parent);
int par_v = Find(v, parent);
if (par_u == par_v)
return new int[] { u, v };
UnionBySize(par_u, par_v, parent);
}
return new int[] { -1, -1 };
}
public static void Main(string[] args) {
int N = 3;
int[][] edges = { new int[] { 1, 2 }, new int[] { 1, 3 }, new int[] { 2, 3 } };
int[] parent = new int[N + 1];
Array.Fill(parent, -1);
int[] redundant = FindRedundantConnection(edges, parent);
if (redundant[0] == -1) {
Console.WriteLine("Not found");
} else {
Console.WriteLine(redundant[0] + " " + redundant[1]);
}
}
}
|
Javascript
function find(node, parent) {
if (parent[node] < 0)
return node;
return parent[node] = find(parent[node], parent);
}
function unionBySize(par_u, par_v, parent) {
if (parent[par_u] < parent[par_v]) {
parent[par_u] += parent[par_v];
parent[par_v] = par_u;
}
else {
parent[par_v] += parent[par_u];
parent[par_u] = par_v;
}
}
function findRedundantConnection(edges, parent) {
for (let edge of edges) {
let u = edge[0], v = edge[1];
let par_u = find(u, parent);
let par_v = find(v, parent);
if (par_u === par_v)
return [u, v];
unionBySize(par_u, par_v, parent);
}
return [-1, -1];
}
const N = 3;
const edges = [[1, 2], [1, 3], [2, 3]];
const parent = new Array(N + 1).fill(-1);
const redundant = findRedundantConnection(edges, parent);
if (redundant[0] === -1) {
console.log("Not found");
}
else {
console.log(redundant[0] + " " + redundant[1]);
}
|
Time complexity: O(E * ????(N)), where N is the number of nodes, E is the number of edges in the graph and ????(N) is the Inverse Ackermann Function which grows very slowly.
Auxiliary Space: O(N), where N is the number of nodes in the graph.
|
