Given an undirected graph, with n nodes numbered from 0 to n-1. Given a 2D integer array of edges where edges[i]= [ai, bi] denotes that there exists an undirected edge between connected nodes ai and bi. The task is to find the ratio between Duplets and Triplets from the given graph where Duplet can be defined as a component with 2 nodes and a Triplet defined as a component with 3 nodes.
Examples:
Input: n = 12, edges = [[0, 1], [1, 3], [2, 6], [2, 5], [6, 11], [11, 5], [7, 9], [8, 4], [8, 10]]
Undirected graph
Output: 1: 2
Explanation: As shown in the above picture, there are 2 triplets and 1 duplet in the graph. So the ratio is 1:2
Approach: The above question can be solved with the following intuition:
A connected component of an undirected graph, as we know, is a subgraph in which each pair of nodes is connected to each other by a path. It means that nodes in a connected component can reach all other nodes in the same connected component. However, if two nodes belong to different components, it is impossible to reach one node from the other. There are total of 4 components in it. We need to find no. of nodes in every component and find their ratio using GCD.
Below are the steps involved in the implementation of the code:
- Create an adjacency list as a ‘graph‘ containing all neighbors of node index i.
- Declare a boolean visited array of size n.
- Declare a temporary ArrayList/vector to store the number of nodes of each component.
- Iterate through all the nodes from 0 to n-1.
- Now call the DFS method if the current node is not visited i.e. if vis[i] is false.
- In the DFS method, count no. of dfs calls made for the neighbor nodes which are unvisited and check whether it is a duplet or triplet as shown in the below code.
- Now, find the ratio of duplet and triplet using the findRatio() method.
- Print the answer.
Below is the implementation of the above approach:
C++
// C++ code for the above approach:#include <bits/stdc++.h>#include <iostream>using namespace std;// Depth first traversalint dfs(vector<vector<int> >& graph, vector<bool>& visited, int node){ visited[node] = true; int no_of_nodes = 1; for (int neighbor : graph[node]) { // If a node is not visited if (!visited[neighbor]) { no_of_nodes += dfs(graph, visited, neighbor); } } return no_of_nodes;}// Function to get gcdint getGCD(int i1, int i2){ if (i1 == i2) return i1; if (i1 > i2) return getGCD(i1 - i2, i2); return getGCD(i1, i2 - i1);}string getRatio(int duplets, int triplets){ int gcd = getGCD(duplets, triplets); int d1 = duplets / gcd; int d2 = triplets / gcd; string ans = ""; ans = to_string(d1) + " : " + to_string(d2); return ans;}// Function to find ratio between duplets// and Triplets in a graphstring findRatio(int n, vector<vector<int> > edges){ vector<vector<int> > graph; for (int i = 0; i < n; i++) { graph.push_back({}); } for (int i = 0; i < edges.size(); i++) { int x = edges[i][0]; int y = edges[i][1]; graph[x].push_back(y); graph[y].push_back(x); } int duplets = 0, triplets = 0; vector<long long> temp; vector<bool> vis(n, false); for (int i = 0; i < n; i++) { // If not visited if (vis[i] == false) { // Calling dfs int no_of_nodes = dfs(graph, vis, i); if (no_of_nodes == 2) { duplets++; } else if (no_of_nodes == 3) { triplets++; } } } string ans = ""; if (duplets == 0 && triplets == 0) { ans = "0 : 0"; } else if (triplets == 0) { ans = to_string(duplets) + " : 0"; } else if (duplets == 0) { ans = "0 : " + to_string(triplets); } else { ans = getRatio(duplets, triplets); } return ans;}// Driver codeint main(){ vector<vector<int> > edges{ { 0, 1 }, { 1, 3 }, { 2, 6 }, { 2, 5 }, { 6, 11 }, { 11, 5 }, { 7, 9 }, { 8, 4 }, { 8, 10 } }; int n = 12; // Function call string ans = findRatio(n, edges); cout << "Ratio is = " << ans << endl; return 0;} |
Java
import java.util.*;public class Main { // Depth first traversal public static int dfs(List<List<Integer>> graph, boolean[] visited, int node) { visited[node] = true; int no_of_nodes = 1; for (int neighbor : graph.get(node)) { // If a node is not visited if (!visited[neighbor]) { no_of_nodes += dfs(graph, visited, neighbor); } } return no_of_nodes; } // Function to get gcd public static int getGCD(int i1, int i2) { if (i1 == i2) { return i1; } if (i1 > i2) { return getGCD(i1 - i2, i2); } return getGCD(i1, i2 - i1); } public static String getRatio(int duplets, int triplets) { int gcd = getGCD(duplets, triplets); int d1 = duplets / gcd; int d2 = triplets / gcd; String ans = d1 + " : " + d2; return ans; } // Function to find ratio between duplets and Triplets in a graph public static String findRatio(int n, List<List<Integer>> edges) { List<List<Integer>> graph = new ArrayList<>(); for (int i = 0; i < n; i++) { graph.add(new ArrayList<>()); } for (int i = 0; i < edges.size(); i++) { int x = edges.get(i).get(0); int y = edges.get(i).get(1); graph.get(x).add(y); graph.get(y).add(x); } int duplets = 0, triplets = 0; boolean[] vis = new boolean[n]; for (int i = 0; i < n; i++) { // If not visited if (!vis[i]) { // Calling dfs int no_of_nodes = dfs(graph, vis, i); if (no_of_nodes == 2) { duplets++; } else if (no_of_nodes == 3) { triplets++; } } } String ans = ""; if (duplets == 0 && triplets == 0) { ans = "0 : 0"; } else if (triplets == 0) { ans = duplets + " : 0"; } else if (duplets == 0) { ans = "0 : " + triplets; } else { ans = getRatio(duplets, triplets); } return ans; } // Driver code public static void main(String[] args) { List<List<Integer>> edges = Arrays.asList( Arrays.asList(0, 1), Arrays.asList(1, 3), Arrays.asList(2, 6), Arrays.asList(2, 5), Arrays.asList(6, 11), Arrays.asList(11, 5), Arrays.asList(7, 9), Arrays.asList(8, 4), Arrays.asList(8, 10) ); int n = 12; // Function call String ans = findRatio(n, edges); System.out.println("Ratio is = " + ans); }} |
Python3
from typing import List# Depth first traversaldef dfs(graph: List[List[int]], visited: List[bool], node: int) -> int: visited[node] = True no_of_nodes = 1 for neighbor in graph[node]: # If a node is not visited if not visited[neighbor]: no_of_nodes += dfs(graph, visited, neighbor) return no_of_nodes# Function to get gcddef get_gcd(i1: int, i2: int) -> int: if i1 == i2: return i1 if i1 > i2: return get_gcd(i1 - i2, i2) return get_gcd(i1, i2 - i1)def get_ratio(duplets: int, triplets: int) -> str: gcd = get_gcd(duplets, triplets) d1 = duplets // gcd d2 = triplets // gcd ans = f"{d1} : {d2}" return ans# Function to find ratio between duplets# and Triplets in a graphdef find_ratio(n: int, edges: List[List[int]]) -> str: graph = [[] for i in range(n)] for i in range(len(edges)): x, y = edges[i][0], edges[i][1] graph[x].append(y) graph[y].append(x) duplets, triplets = 0, 0 vis = [False] * n for i in range(n): # If not visited if not vis[i]: # Calling dfs no_of_nodes = dfs(graph, vis, i) if no_of_nodes == 2: duplets += 1 elif no_of_nodes == 3: triplets += 1 ans = "" if duplets == 0 and triplets == 0: ans = "0 : 0" elif triplets == 0: ans = f"{duplets} : 0" elif duplets == 0: ans = f"0 : {triplets}" else: ans = get_ratio(duplets, triplets) return ans# Driver codeif __name__ == '__main__': edges = [ [0, 1], [1, 3], [2, 6], [2, 5], [6, 11], [11, 5], [7, 9], [8, 4], [8, 10] ] n = 12 # Function call ans = find_ratio(n, edges) print("Ratio is =", ans) |
C#
// C# code to implement the above approach.using System;using System.Collections.Generic;public class MainClass{ // Depth first traversal public static int dfs(List<List<int>> graph, bool[] visited, int node) { visited[node] = true; int no_of_nodes = 1; foreach (int neighbor in graph[node]) { // If a node is not visited if (!visited[neighbor]) { no_of_nodes += dfs(graph, visited, neighbor); } } return no_of_nodes; } // Function to get gcd public static int getGCD(int i1, int i2) { if (i1 == i2) { return i1; } if (i1 > i2) { return getGCD(i1 - i2, i2); } return getGCD(i1, i2 - i1); } public static string getRatio(int duplets, int triplets) { int gcd = getGCD(duplets, triplets); int d1 = duplets / gcd; int d2 = triplets / gcd; string ans = d1 + " : " + d2; return ans; } // Function to find ratio between duplets and Triplets in a graph public static string findRatio(int n, List<List<int>> edges) { List<List<int>> graph = new List<List<int>>(); for (int i = 0; i < n; i++) { graph.Add(new List<int>()); } for (int i = 0; i < edges.Count; i++) { int x = edges[i][0]; int y = edges[i][1]; graph[x].Add(y); graph[y].Add(x); } int duplets = 0, triplets = 0; bool[] vis = new bool[n]; for (int i = 0; i < n; i++) { // If not visited if (!vis[i]) { // Calling dfs int no_of_nodes = dfs(graph, vis, i); if (no_of_nodes == 2) { duplets++; } else if (no_of_nodes == 3) { triplets++; } } } string ans = ""; if (duplets == 0 && triplets == 0) { ans = "0 : 0"; } else if (triplets == 0) { ans = duplets + " : 0"; } else if (duplets == 0) { ans = "0 : " + triplets; } else { ans = getRatio(duplets, triplets); } return ans; } // Driver code public static void Main(string[] args) { List<List<int>> edges = new List<List<int>>() { new List<int> { 0, 1 }, new List<int> { 1, 3 }, new List<int> { 2, 6 }, new List<int> { 2, 5 }, new List<int> { 6, 11 }, new List<int> { 11, 5 }, new List<int> { 7, 9 }, new List<int> { 8, 4 }, new List<int> { 8, 10 } }; int n = 12; // Function call string ans = findRatio(n, edges); Console.WriteLine("Ratio is = " + ans); }}// This code is contributed by Vaibhav Nandan |
Javascript
function dfs(graph, visited, node) { visited[node] = true; let no_of_nodes = 1; for (let neighbor of graph[node]) { // If a node is not visited if (!visited[neighbor]) { no_of_nodes += dfs(graph, visited, neighbor); } } return no_of_nodes;}function getGCD(i1, i2) { if (i1 == i2) { return i1; } if (i1 > i2) { return getGCD(i1 - i2, i2); } return getGCD(i1, i2 - i1);}function getRatio(duplets, triplets) { const gcd = getGCD(duplets, triplets); const d1 = duplets / gcd; const d2 = triplets / gcd; const ans = `${d1} : ${d2}`; return ans;}function findRatio(n, edges) { const graph = new Array(n).fill().map(() => new Array()); for (let i = 0; i < edges.length; i++) { const [x, y] = edges[i]; graph[x].push(y); graph[y].push(x); } let duplets = 0, triplets = 0; const vis = new Array(n).fill(false); for (let i = 0; i < n; i++) { // If not visited if (!vis[i]) { // Calling dfs const no_of_nodes = dfs(graph, vis, i); if (no_of_nodes === 2) { duplets++; } else if (no_of_nodes === 3) { triplets++; } } } let ans = ""; if (duplets === 0 && triplets === 0) { ans = "0 : 0"; } else if (triplets === 0) { ans = `${duplets} : 0`; } else if (duplets === 0) { ans = `0 : ${triplets}`; } else { ans = getRatio(duplets, triplets); } return ans;}// Driver codeconst edges = [ [0, 1], [1, 3], [2, 6], [2, 5], [6, 11], [11, 5], [7, 9], [8, 4], [8, 10]];const n = 12;const answer = findRatio(n, edges);console.log(`Ratio is = ${answer}`); |
Output
Ratio is = 1 : 2
Time Complexity: O(N + E)[DFS] + O(log(min(a, b))
Auxiliary Space: O(N+E)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Share your thoughts in the comments
