Minimum Score in an Undirected Graph
Given an undirected graph find all the cycles of length 3 and calculate the minimum score among all these cycles. The score of a cycle is the total number of edges which are not part of the current cycle but are connected to any one of the three nodes of the cycle.
If there is no cycle of three nodes, return -1.
Asked in PAYPAL INTERVIEW
Examples:
Input: V= 6, E = 6, edges = [[1, 2], [2, 4], [2, 5], [3, 5], [4, 5], [5, 6]]
Output: 3
Explanation:Number of edges not in the cycle but connected to 2 is 1
Number of edges not in the cycle but connected to 4 is 0
Number of edges not in the cycle but connected to 5 is 2
Sum of total count = 3Input: V = 6, E = 5, edges = [[1, 2], [2, 3], [3, 4], [4, 5], [5, 6]]
Output: -1
Explanation: No cycle is present in the graph
Approach:
We can solve the problem by using DFS on the graph and maintaining a parent array to store the parent of every node. Now, while traversing through all the nodes if we encounter a node which is already visited and the nodes is not the parent of current node, then it means we have found a cycle in the graph. We can then check for the length of cycle to be 3 and minimize our answer with this cycle.
Steps to solve the problem:
- Maintain a parent array par[] to store the parent of the nodes.
- Traverse through the graph and if we encounter a visited node which is not the parent of the current node, then we have found a cycle in our graph.
- Check if the grand parent of current node is same as the visited node.
- If yes, then the cycle has a length of 3, so minimize the answer with the current cycle.
Below is the Implementation for this Approach :-
C++
#include <iostream> #include <vector> #include <climits> using namespace std; int ans = INT_MAX; // Function to find cycles in the graph using depth-first search void findCycles( int node, vector<vector< int >>& adj, vector< int >& par, int parent) { // Mark the current node as visited par[node] = parent; for ( int child : adj[node]) { if (par[child] == INT_MIN) { // If the child is not visited, explore this child findCycles(child, adj, par, node); } else if (child != parent) { // If the child is visited and is not the parent of the current node // Check length of cycle to be 3 if (parent != -1 && par[parent] == child) { // Count all the edges of the three nodes int edges = adj[child].size() + adj[node].size() + adj[parent].size(); // Subtract 6 as the edges in the cycle are also counted twice in our answer if (edges - 6 < ans) ans = edges - 6; } } } } // Function to calculate the Trio Score void getMinScore( int V, vector<vector< int >>& edges) { vector<vector< int >> adj(V + 1); vector< int > par(V + 1, INT_MIN); // Create an adjacency list to represent the graph for ( auto & edge : edges) { adj[edge[0]].push_back(edge[1]); adj[edge[1]].push_back(edge[0]); } // Run DFS for all connected components for ( int i = 1; i <= V; i++) { if (par[i] == INT_MIN) { findCycles(i, adj, par, -1); } } } int main() { // Number of nodes int V = 6; // Edge List vector<vector< int >> edges = {{1, 2}, {2, 4}, {2, 5}, {3, 5}, {4, 5}, {5, 6}}; // Method to calculate answer getMinScore(V, edges); if (ans == INT_MAX) cout << -1 << endl; else cout << ans << endl; return 0; } |
Java
// java program to find the trio score import java.util.*; class Main { static int ans = Integer.MAX_VALUE; // Function to find cycles in the graph using // depth-first search static void findCycles( int node, List<List<Integer> > adj, List<Integer> par, int parent) { // Mark the current node as visited par.set(node, parent); for ( int child : adj.get(node)) { if (par.get(child) == Integer.MIN_VALUE) { // If the child is not visited, // explore this child findCycles(child, adj, par, node); } // If the child is visited and is // not the parent of current node else if (child != parent) { // Check length of cycle to be 3 if (parent != - 1 && par.get(parent) == child) { // Count all the edges of the three // nodes int edges = adj.get(child).size() + adj.get(node).size() + adj.get(parent).size(); // Subtract 6 as the edges in the cycle // are also counted twice in our answer if (edges - 6 < ans) ans = edges - 6 ; } } } } // Function to calculate the Trio Score static void getMinScore( int V, List<List<Integer> > edges) { List<List<Integer> > adj = new ArrayList<>(); List<Integer> par = new ArrayList<>(); for ( int i = 0 ; i <= V; i++) { adj.add( new ArrayList<>()); par.add(Integer.MIN_VALUE); } // Create an adjacency list to represent // the graph for (List<Integer> edge : edges) { adj.get(edge.get( 0 )).add(edge.get( 1 )); adj.get(edge.get( 1 )).add(edge.get( 0 )); } // Run DFS for all connected components for ( int i = 1 ; i <= V; i++) { if (par.get(i) == Integer.MIN_VALUE) { findCycles(i, adj, par, - 1 ); } } } public static void main(String[] args) { // Number of nodes int V = 6 ; // Edge List List<List<Integer> > edges = new ArrayList<List<Integer> >(); edges.add(Arrays.asList( 1 , 2 )); edges.add(Arrays.asList( 2 , 4 )); edges.add(Arrays.asList( 2 , 5 )); edges.add(Arrays.asList( 3 , 5 )); edges.add(Arrays.asList( 4 , 5 )); edges.add(Arrays.asList( 5 , 6 )); // Method to calculate answer getMinScore(V, edges); if (ans == Integer.MAX_VALUE) System.out.println(- 1 ); else System.out.println(ans); } } |
Python3
from collections import defaultdict # Global variable to store the minimum trio score ans = float ( 'inf' ) # Function to find cycles in the graph using depth-first search def find_cycles(node, adj, par, parent): global ans # Mark the current node as visited par[node] = parent for child in adj[node]: if par[child] = = - 1 : # If the child is not visited, explore this child find_cycles(child, adj, par, node) # If the child is visited and is not the parent of the current node elif child ! = parent: # Check the length of the cycle to be 3 if parent ! = - 1 and par[parent] = = child: # Count all the edges of the three nodes edges = len (adj[child]) + len (adj[node]) + len (adj[parent]) # Subtract 6 as the edges in the cycle are also counted twice in our answer ans = min (ans, edges - 6 ) # Function to calculate the Trio Score def get_min_score(V, edges): global ans adj = defaultdict( list ) par = [ - 1 ] * (V + 1 ) # Create an adjacency list to represent the graph for edge in edges: adj[edge[ 0 ]].append(edge[ 1 ]) adj[edge[ 1 ]].append(edge[ 0 ]) # Run DFS for all connected components for i in range ( 1 , V + 1 ): if par[i] = = - 1 : find_cycles(i, adj, par, - 1 ) # Driver code if __name__ = = "__main__" : # Number of nodes V = 6 # Edge List edges = [[ 1 , 2 ], [ 2 , 4 ], [ 2 , 5 ], [ 3 , 5 ], [ 4 , 5 ], [ 5 , 6 ]] # Method to calculate answer get_min_score(V, edges) if ans = = float ( 'inf' ): print ( - 1 ) else : print (ans) |
C#
using System; using System.Collections.Generic; class Program { static int ans = int .MaxValue; // Function to find cycles in the graph using depth-first search static void FindCycles( int node, List<List< int >> adj, List< int > par, int parent) { // Mark the current node as visited par[node] = parent; foreach ( int child in adj[node]) { if (par[child] == int .MinValue) { // If the child is not visited, explore this child FindCycles(child, adj, par, node); } else if (child != parent) { // If the child is visited and is not the parent of the current node // Check length of cycle to be 3 if (parent != -1 && par[parent] == child) { // Count all the edges of the three nodes int edges = adj[child].Count + adj[node].Count + adj[parent].Count; // Subtract 6 as the edges in the cycle are also counted twice in our answer if (edges - 6 < ans) ans = edges - 6; } } } } // Function to calculate the Trio Score static void GetMinScore( int V, List<List< int >> edges) { List<List< int >> adj = new List<List< int >>(V + 1); for ( int i = 0; i <= V; i++) { adj.Add( new List< int >()); } List< int > par = new List< int >(V + 1); for ( int i = 0; i <= V; i++) { par.Add( int .MinValue); } // Create an adjacency list to represent the graph foreach ( var edge in edges) { adj[edge[0]].Add(edge[1]); adj[edge[1]].Add(edge[0]); } // Run DFS for all connected components for ( int i = 1; i <= V; i++) { if (par[i] == int .MinValue) { FindCycles(i, adj, par, -1); } } } static void Main() { // Number of nodes int V = 6; // Edge List List<List< int >> edges = new List<List< int >> { new List< int > {1, 2}, new List< int > {2, 4}, new List< int > {2, 5}, new List< int > {3, 5}, new List< int > {4, 5}, new List< int > {5, 6} }; // Method to calculate answer GetMinScore(V, edges); if (ans == int .MaxValue) Console.WriteLine(-1); else Console.WriteLine(ans); } } |
Javascript
// Javascript code for the above approach let ans = Number.MAX_VALUE; // Function to find cycles in the graph // using depth-first search function findCycles(node, adj, par, parent) { // Mark the current node as visited par[node] = parent; for (let child of adj[node]) { if (par[child] == Number.MIN_VALUE) { // If the child is not visited, explore this child findCycles(child, adj, par, node); } else if (child != parent) { // If the child is visited and is not the // parent of the current node // Check length of cycle to be 3 if (parent != -1 && par[parent] == child) { // Count all the edges of the three nodes const edges = adj[child].length + adj[node].length + adj[parent].length; // Subtract 6 as the edges in the cycle // are also counted twice in our answer if (edges - 6 < ans) { ans = edges - 6; } } } } } // Function to calculate the Trio Score function getMinScore(V, edges) { const adj = Array.from({ length: V + 1 }, () => []); const par = Array(V + 1).fill(Number.MIN_VALUE) // Create an adjacency list to represent the graph for (const edge of edges) { adj[edge[0]].push(edge[1]); adj[edge[1]].push(edge[0]); } // console.log(adj) // console.log(par) // Run DFS for all connected components for (let i = 1; i <= V; i++) { if (par[i] == Number.MIN_VALUE) { findCycles(i, adj, par, -1); } } } // Driver code function main() { // Number of nodes const V = 6; // Edge List const edges = [ [1, 2], [2, 4], [2, 5], [3, 5], [4, 5], [5, 6] ]; // Method to calculate answer getMinScore(V, edges); if (ans === Number.MAX_VALUE) console.log(-1); else console.log(ans); } // Driver function call main() // This code is contributed by ragul21 |
3
Time Complexity: O(V + E) , where V is number of vertices and E is number of edges.
Auxiliary Space: O(V + E)
Contact Us