Given an integer N, representing the number of nodes present in an undirected graph, with each node valued from 1 to N, and a 2D array Edges[][], representing the pair of vertices connected by an edge, the task is to find a set of at most N/2 nodes such that nodes that are not present in the set, are connected adjacent to any one of the nodes present in the set.
Examples :
Input: N = 4, Edges[][2] = {{2, 3}, {1, 3}, {4, 2}, {1, 2}}
Output: 3 2
Explanation: Connections specified in the above graph are as follows:
1
/ \
2 – 3
|
4
Selecting the set {2, 3} satisfies the required conditions.Input: N = 5, Edges[][2] = {{2, 1}, {3, 1}, {3, 2}, {4, 1}, {4, 2}, {4, 3}, {5, 1}, {5, 2}, {5, 3}, {5, 4}}
Output: 1
Approach: The given problem can be solved based on the following observations:
- Assume a node to be the source node, then the distance of each vertex from the source node will be either odd or even.
- Split the nodes into two different sets based on parity, the size of at least one of the sets will not exceed N/2. Since each node of some parity is connected to at least one node of opposite parity, the criteria of choosing at most N/2 nodes is satisfied.
Follow the steps below to solve the problem:
- Assume any vertex to be the source node.
- Initialize two sets, say evenParity and oddParity, to store the nodes having even and odd distances from the source node respectively.
- Perform BFS Traversal on the given graph and split the vertices into two different sets depending on the parity of their distances from the source:
- If the distance of each connected node from the source node is odd, then insert the current node in the set oddParity.
- If the distance of each connected node from the source node is even, then insert the current node in the set evenParity.
- After completing the above steps, print the elements of the set with the minimum size.
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to add an edge// to the adjacency listvoid addEdge(vector<vector<int> >& adj, int u, int v){ adj[u].push_back(v); adj[v].push_back(u);}// Function to perform BFS// traversal on a given graphvector<vector<int> > BFS( int N, int source, vector<vector<int> > adjlist){ // Stores the distance of each // node from the source node int dist[N + 1]; vector<vector<int> > vertex_set; // Update the distance of all // vertices from source as -1 memset(dist, -1, sizeof dist); // Assign two separate vectors // for parity odd and even parities vertex_set.assign(2, vector<int>(0)); // Perform BFS Traversal queue<int> Q; // Push the source node Q.push(source); dist = 0; // Iterate until queue becomes empty while (!Q.empty()) { // Get the front node // present in the queue int u = Q.front(); Q.pop(); // Push the node into vertex_set vertex_set[dist[u] % 2].push_back(u); // Check if the adjacent // vertices are visited for (int i = 0; i < (int)adjlist[u].size(); i++) { // Adjacent node int v = adjlist[u][i]; // If the node v is unvisited if (dist[v] == -1) { // Update the distance dist[v] = dist[u] + 1; // Enqueue the node v Q.push(v); } } } // Return the possible set of nodes return vertex_set;}// Function to find a set of vertices// of at most N/2 nodes such that each// unchosen node is connected adjacently// to one of the nodes in the setvoid findSet(int N, vector<vector<int> > adjlist){ // Source vertex int source = 1; // Store the vertex set vector<vector<int> > vertex_set = BFS(N, source, adjlist); // Stores the index // with minimum size int in = 0; if (vertex_set[1].size() < vertex_set[0].size()) in = 1; // Print the nodes present in the set for (int node : vertex_set[in]) { cout << node << " "; }}// Driver Codeint main(){ int N = 5; int M = 8; vector<vector<int> > adjlist; adjlist.assign(N + 1, vector<int>(0)); // Graph Formation addEdge(adjlist, 2, 5); addEdge(adjlist, 2, 1); addEdge(adjlist, 5, 1); addEdge(adjlist, 4, 5); addEdge(adjlist, 1, 4); addEdge(adjlist, 2, 4); addEdge(adjlist, 3, 4); addEdge(adjlist, 3, 5); // Function Call to print the // set of at most N / 2 nodes findSet(N, adjlist); return 0;} |
Python3
# Python3 program for the above approachfrom collections import deque# Function to add an edge# to the adjacency listdef addEdge(adj, u, v): adj[u].append(v) adj[v].append(u) return adj# Function to perform BFS# traversal on a given graphdef BFS(N, source, adjlist): # Stores the distance of each # node from the source node dist = [-1]*(N + 1) vertex_set = [[] for i in range(2)] # Perform BFS Traversal Q = deque() # Push the source node Q.append(source) dist = 0 # Iterate until queue becomes empty while len(Q) > 0: # Get the front node # present in the queue u = Q.popleft() # Push the node into vertex_set vertex_set[dist[u] % 2].append(u) # Check if the adjacent # vertices are visited for i in range(len(adjlist[u])): # Adjacent node v = adjlist[u][i] # If the node v is unvisited if (dist[v] == -1): # Update the distance dist[v] = dist[u] + 1 # Enqueue the node v Q.append(v) # Return the possible set of nodes return vertex_set# Function to find a set of vertices# of at most N/2 nodes such that each# unchosen node is connected adjacently# to one of the nodes in the setdef findSet(N, adjlist): # Source vertex source = 1 # Store the vertex set vertex_set = BFS(N, source, adjlist) # Stores the index # with minimum size inn = 0 if (len(vertex_set[1]) < len(vertex_set[0])): inn = 1 # Print the nodes present in the set for node in vertex_set[inn]: print(node, end=" ")# Driver Codeif __name__ == '__main__': N = 5 M = 8 adjlist = [[] for i in range(N+1)] # Graph Formation adjlist = addEdge(adjlist, 2, 5) adjlist = addEdge(adjlist, 2, 1) adjlist = addEdge(adjlist, 5, 1) adjlist = addEdge(adjlist, 4, 5) adjlist = addEdge(adjlist, 1, 4) adjlist = addEdge(adjlist, 2, 4) adjlist = addEdge(adjlist, 3, 4) adjlist = addEdge(adjlist, 3, 5) # Function Call to print the # set of at most N / 2 nodes findSet(N, adjlist)# This code is contributed by mohit kumar 29. |
Java
import java.util.LinkedList;import java.util.Queue;class Main {static void addEdge(LinkedList<Integer>[] adj, int u, int v) {adj[u].add(v);adj[v].add(u);}static LinkedList<Integer>[] BFS(int N, int source, LinkedList<Integer>[] adjlist) { int[] dist = new int[N+1]; for (int i = 0; i <= N; i++) { dist[i] = -1; } LinkedList<Integer>[] vertex_set = new LinkedList[2]; vertex_set[0] = new LinkedList<Integer>(); vertex_set[1] = new LinkedList<Integer>(); // Perform BFS Traversal Queue<Integer> Q = new LinkedList<Integer>(); // Push the source node Q.add(source); dist = 0; // Iterate until queue becomes empty while (Q.size() > 0) { int u = Q.remove(); vertex_set[dist[u] % 2].add(u); for (Integer v : adjlist[u]) { // If the node v is unvisited if (dist[v] == -1) { // Update the distance dist[v] = dist[u] + 1; // Enqueue the node v Q.add(v); } } } // Return the possible set of nodes return vertex_set;}// Function to find a set of vertices// of at most N/2 nodes such that each// unchosen node is connected adjacently// to one of the nodes in the setstatic void findSet(int N, LinkedList<Integer>[] adjlist) { // Source vertex int source = 1; // Store the vertex set LinkedList<Integer>[] vertex_set = BFS(N, source, adjlist); // Stores the index // with minimum size int inn = 0; if (vertex_set[1].size() < vertex_set[0].size()) { inn = 1; } // Print the nodes present in the set for (int node : vertex_set[inn]) { System.out.print(node + " "); }}public static void main(String[] args) { int N = 5; int M = 8; LinkedList<Integer>[] adjlist = new LinkedList[N+1]; for (int i = 0; i <= N; i++) { adjlist[i] = new LinkedList<Integer>(); } // Graph Formation addEdge(adjlist, 2, 5); addEdge(adjlist, 2, 1); addEdge(adjlist, 5, 1); addEdge(adjlist, 4, 5); addEdge(adjlist, 1, 4); addEdge(adjlist, 2, 4); addEdge(adjlist, 3, 4); addEdge(adjlist, 3, 5); findSet(N, adjlist); }} |
Javascript
// This function adds an edge to an adjacency listfunction addEdge(adj, u, v) { adj[u].push(v); // Add v to the adjacency list of u adj[v].push(u); // Add u to the adjacency list of v return adj; // Return the updated adjacency list}// This function performs a BFS on a graph represented as an adjacency listfunction BFS(N, source, adjlist) { let dist = new Array(N + 1).fill(-1); // Array to store the distance of each vertex from the source let vertex_set = [[], []]; // Two sets to store the vertices with even and odd distances from the source let Q = []; // Queue to store the vertices to be visited Q.push(source); // Enqueue the source vertex dist = 0; // The distance of the source vertex from itself is 0 while (Q.length > 0) { // Continue BFS until the queue is empty let u = Q.shift(); // Dequeue a vertex from the queue vertex_set[dist[u] % 2].push(u); // Add the vertex to the set corresponding to its distance from the source for (let i = 0; i < adjlist[u].length; i++) { // Visit all neighbors of the current vertex let v = adjlist[u][i]; // Get the i-th neighbor of u if (dist[v] === -1) { // If v has not been visited yet dist[v] = dist[u] + 1; // Update the distance of v from the source Q.push(v); // Enqueue v for later processing } } } return vertex_set; // Return the two sets of vertices}// This function finds the vertex set with fewer vertices with odd distance from the sourcefunction findSet(N, adjlist) { let source = 1; // The source vertex for BFS let vertex_set = BFS(N, source, adjlist); // Find the sets of vertices with even and odd distances from the source let inn = 0; // Index of the set with fewer vertices with odd distance from the source if (vertex_set[1].length < vertex_set[0].length) { // If the set of vertices with odd distance is smaller inn = 1; // Set the index to 1 } for (let node of vertex_set[inn]) { // For each node in the smaller set console.log(node); // Output the node }}let N = 5; // Number of verticeslet M = 8; // Number of edgeslet adjlist = new Array(N + 1).fill([]); // Initialize an empty adjacency list for each vertex// Add the edges to the graphadjlist = addEdge(adjlist, 2, 5);adjlist = addEdge(adjlist, 2, 1);adjlist = addEdge(adjlist, 5, 1);adjlist = addEdge(adjlist, 4, 5);adjlist = addEdge(adjlist, 1, 4);adjlist = addEdge(adjlist, 2, 4);adjlist = addEdge(adjlist, 3, 4);adjlist = addEdge(adjlist, 3, 5);findSet(N, adjlist); // Find the set of vertices with fewer vertices with odd distance from the source vertex |
C#
using System;using System.Collections.Generic;class Program{ // Function to add an edge // to the adjacency list static void AddEdge(List<List<int>> adj, int u, int v) { adj[u].Add(v); adj[v].Add(u); } // Function to perform BFS // traversal on a given graph static List<List<int>> BFS(int N, int source, List<List<int>> adjlist) { // Stores the distance of each // node from the source node int[] dist = new int[N + 1]; for (int i = 0; i < dist.Length; i++) { dist[i] = -1; } List<List<int>> vertex_set = new List<List<int>>(); // Assign two separate lists // for parity odd and even parities vertex_set.Add(new List<int>()); vertex_set.Add(new List<int>()); // Perform BFS Traversal Queue<int> Q = new Queue<int>(); // Push the source node Q.Enqueue(source); dist = 0; // Iterate until queue becomes empty while (Q.Count > 0) { // Get the front node // present in the queue int u = Q.Dequeue(); // Push the node into vertex_set vertex_set[dist[u] % 2].Add(u); // Check if the adjacent // vertices are visited for (int i = 0; i < adjlist[u].Count; i++) { // Adjacent node int v = adjlist[u][i]; // If the node v is unvisited if (dist[v] == -1) { // Update the distance dist[v] = dist[u] + 1; // Enqueue the node v Q.Enqueue(v); } } } // Return the possible set of nodes return vertex_set; } // Function to find a set of vertices // of at most N/2 nodes such that each // unchosen node is connected adjacently // to one of the nodes in the set static void FindSet(int N, List<List<int>> adjlist) { // Source vertex int source = 1; // Store the vertex set List<List<int>> vertex_set = BFS(N, source, adjlist); // Stores the index // with minimum size int inIndex = 0; if (vertex_set[1].Count < vertex_set[0].Count) { inIndex = 1; } // Print the nodes present in the set foreach (int node in vertex_set[inIndex]) { Console.Write(node + " "); } } // Driver Code static void Main(string[] args) { int N = 5; int M = 8; List<List<int>> adjlist = new List<List<int>>(); for (int i = 0; i < N + 1; i++) { adjlist.Add(new List<int>()); } // Graph Formation AddEdge(adjlist, 2, 5); AddEdge(adjlist, 2, 1); AddEdge(adjlist, 5, 1); AddEdge(adjlist, 4, 5); AddEdge(adjlist, 1, 4); AddEdge(adjlist, 2, 4); AddEdge(adjlist, 3, 4); AddEdge(adjlist, 3, 5); // Function Call to print the // set of at most N / 2 nodes FindSet(N, adjlist); }} |
Output:
1 3
Time Complexity: O(N + M)
Auxiliary Space: O(N + M)
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!
