Given a graph with N vertices numbered from 0 to (N-1) and a matrix edges[][] representing the edges of the graph, the task is to find out the maximum number of pairs that can be formed where each element of a pair belongs to different connected components of the graph.
Examples:
Input: N = 4, edges = {{1, 2}, {2, 3}}
Output: 3
Explanation: Total nodes 4 (from 0 to 3).
There are 3 possible pairs: {0, 1}, {0, 2} and {0, 3}.
No pair between {1, 2} or {1, 3} or {2, 3} because they belong to the same connected component.
graph with given edges
Input: N = 2, edges = {0, 1}
Output: 0
Explanation: All the elements belong to the same connected component.
Approach: The problem can be solved by counting the number of connected components and the number of nodes in each connected component. Total N*(N-1)/2 nodes can be formed from the given N nodes. But, to get the required number of pairs subtract the number of pairs that can be formed among the nodes of each connected component. Follow the steps mentioned below:
- Initiate total as the total number of possible pairs which is N*(N-1)/2.
- Use DFS to find the different connected components and for each component:
- Find out the number of nodes in that connected component and store that in a variable (say cnt).
- Subtract the number of pairs that can be formed by these nodes among themselves i.e. cnt*(cnt – 1)/2.
- After all the nodes are visited, the remaining value of total is the final answer.
Below is the implementation of the above approach
C++
// C++ code to implement the approach#include <bits/stdc++.h>using namespace std;// DFS functionvoid dfs(vector<int> adj[], int src, bool visited[], int& cnt){ visited[src] = true; // Count number of nodes // in current component cnt++; for (auto it : adj[src]) { if (!visited[it]) { dfs(adj, it, visited, cnt); } }}// Function to count total possible pairsint maxPairs(int N, vector<vector<int> >& edges){ vector<int> adj[N]; // Building the adjacency matrix for (int i = 0; i < edges.size(); i++) { adj[edges[i][0]].push_back( edges[i][1]); adj[edges[i][1]].push_back( edges[i][0]); } // Maximum total pairs int total = N * (N - 1) / 2; // Array to keep track of components bool visited[N + 1] = { false }; // Loop to count total possible pairs for (int i = 0; i < N; i++) { if (visited[i] == false) { int cnt = 0; dfs(adj, i, visited, cnt); // Subtract pairs from // the same connected component total -= (cnt * (cnt - 1) / 2); } } return total;}// Driver codeint main(){ int N = 4; vector<vector<int> > edges = { { 1, 2 }, { 2, 3 } }; int result = maxPairs(N, edges); cout << result; return 0;} |
Java
import java.io.*;import java.util.*;class GFG { static int count = 0; // DFS function public static void dfs(ArrayList<ArrayList<Integer> > adj, int src, boolean visited[]) { visited[src] = true; // Count number of nodes // in current component count++; for (int it : adj.get(src)) { if (!visited[it]) { dfs(adj, it, visited); } } } // Function to count total possible pairs public static int maxPairs(int N, ArrayList<ArrayList<Integer> > edges) { ArrayList<ArrayList<Integer> > adj = new ArrayList<ArrayList<Integer> >(); for (int i = 0; i < N; i++) { ArrayList<Integer> temp = new ArrayList<Integer>(); adj.add(temp); } // Building the adjacency matrix for (int i = 0; i < edges.size(); i++) { ArrayList<Integer> temp = adj.get(edges.get(i).get(0)); temp.add(edges.get(i).get(1)); adj.set(edges.get(i).get(0), temp); temp = adj.get(edges.get(i).get(1)); temp.add(edges.get(i).get(0)); adj.set(edges.get(i).get(1), temp); } // Maximum total pairs int total = N * (N - 1) / 2; // Array to keep track of components boolean[] visited = new boolean[N + 1]; for (int i = 0; i <= N; i++) { visited[i] = false; } // Loop to count total possible pairs for (int i = 0; i < N; i++) { if (visited[i] == false) { count = 0; dfs(adj, i, visited); // Subtract pairs from // the same connected component total -= (count * (count - 1) / 2); } } return total; } // Driver code public static void main(String[] args) { int N = 4; ArrayList<ArrayList<Integer> > edges = new ArrayList<ArrayList<Integer> >(); edges.add( new ArrayList<Integer>(Arrays.asList(1, 2))); edges.add( new ArrayList<Integer>(Arrays.asList(2, 3))); int result = maxPairs(N, edges); System.out.println(result); }}// This code is contributed by Palak Gupta |
Python3
# python3 code to implement the approachvisited = []cnt = 0# DFS functiondef dfs(adj, src): global visited global cnt visited[src] = True # Count number of nodes # in current component cnt += 1 for it in adj[src]: if (not visited[it]): dfs(adj, it)# Function to count total possible pairsdef maxPairs(N, edges): global visited global cnt adj = [[] for _ in range(N)] # Building the adjacency matrix for i in range(0, len(edges)): adj[edges[i][0]].append(edges[i][1]) adj[edges[i][1]].append(edges[i][0]) # Maximum total pairs total = (N * (N - 1)) // 2 # Array to keep track of components for i in range(N + 1): visited.append(False) # Loop to count total possible pairs for i in range(0, N): if (visited[i] == False): cnt = 0 dfs(adj, i) # Subtract pairs from # the same connected component total -= ((cnt * (cnt - 1)) // 2) return total# Driver codeif __name__ == "__main__": N = 4 edges = [[1, 2], [2, 3]] result = maxPairs(N, edges) print(result) # This code is contributed by rakeshsahni |
C#
using System;using System.Collections.Generic;class GFG{ static int count = 0; // DFS function public static void dfs(List<List<int>> adj, int src, bool[] visited) { visited[src] = true; // Count number of nodes // in current component count++; foreach (int it in adj[src]) { if (!visited[it]) { dfs(adj, it, visited); } } } // Function to count total possible pairs public static int maxPairs(int N, List<List<int>> edges) { List<List<int>> adj = new List<List<int>>(); for (int i = 0; i < N; i++) { List<int> temp = new List<int>(); adj.Add(temp); } // Building the adjacency matrix for (int i = 0; i < edges.Count; i++) { List<int> temp = adj[edges[i][0]]; temp.Add(edges[i][1]); adj[edges[i][0]] = temp; temp = adj[edges[i][1]]; temp.Add(edges[i][0]); adj[edges[i][1]] = temp; } // Maximum total pairs int total = N * (N - 1) / 2; // Array to keep track of components bool[] visited = new bool[N + 1]; for (int i = 0; i <= N; i++) { visited[i] = false; } // Loop to count total possible pairs for (int i = 0; i < N; i++) { if (visited[i] == false) { count = 0; dfs(adj, i, visited); // Subtract pairs from // the same connected component total -= (count * (count - 1) / 2); } } return total; } // Driver code public static void Main() { int N = 4; List<List<int>> edges = new List<List<int>>(); edges.Add(new List<int>()); edges.Add(new List<int>()); edges[0].Add(1); edges[0].Add(2); edges[1].Add(2); edges[1].Add(3); int result = maxPairs(N, edges); Console.Write(result); }}// This code is contributed by Saurabh Jaiswal |
Javascript
<script> // JavaScript code for the above approach // DFS function function dfs(adj, src, visited, cnt) { visited[src] = true; // Count number of nodes // in current component cnt++; for (let it of adj[src]) { if (!visited[it]) { dfs(adj, it, visited, cnt); } } return cnt; } // Function to count total possible pairs function maxPairs(N, edges) { let adj = new Array(N).fill([]); // Building the adjacency matrix for (let i = 0; i < edges.length; i++) { adj[edges[i][0]].push( edges[i][1]); adj[edges[i][1]].push( edges[i][0]); } // Maximum total pairs let total = N * (N - 1) / 2; // Array to keep track of components let visited = new Array(N + 1).fill(false) // Loop to count total possible pairs for (let i = 0; i < N; i++) { if (visited[i] == false) { let cnt = 0; dfs(adj, i, visited, cnt); // Subtract pairs from // the same connected component total -= (cnt * (cnt - 1) / 2); } } return total / 2; } // Driver code let N = 4; let edges = [[1, 2], [2, 3]]; let result = maxPairs(N, edges); document.write(result); // This code is contributed by Potta Lokesh </script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
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!
