Minimum nodes to be colored in a Graph such that every node has a colored neighbour

0 0 7 minutes read

Given a graph G with V nodes and E edges, the task is to colour no more than floor(V/2) nodes such that every node has at least one coloured node at a distance of atmost 1 unit. The distance between any two connected nodes of the graph is always exactly 1 unit. Print the nodes that need to be colored.

Examples:

Input: N = 4,
G:

Output: 1

Input: N = 6,
G:

Output: 3

Approach: This problem can be solved using BFS traversal. Follow the steps below to solve the problem:

Initialize arrays odd[] and even[] to store nodes which are at a distance of odd and even number of nodes respectively from the source.
Starting from the source node, perform BFS traversal with distance initialized 0, which denotes the distance from source node. Store all the nodes at a particular level in odd[] or even[] based on the value of distance.
If distance is odd, that is (distance & 1) is 1, insert that node into odd[]. Otherwise, insert into even[].
Now print the nodes from the array with minimum elements.
Since minimum among count of nodes at odd distance or even distance does not exceed floor(V/2), the answer holds correct as every node at odd distance is connected to nodes at even distance and vice-versa.
Hence, if number of nodes at even distance from source is less, print the nodes from even[]. Otherwise, print all nodes from odd[].

Illustration:
For the graph G given below,
Source Node S = 1

even[] = {1, 3, 5}

odd[] = {2, 6, 4}

minimum(even.size(), odd.size()) = min(3, 3) = 3

Hence, coloring either all nodes at odd distance from the source or even distance from the source is correct as both their count is same.

Below is the implementation of the above approach:

C++

// C++ Program to implement the
// above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Stores the graph
map<int, vector<int> > graph;
 
// Stores the visited nodes
map<int, int> vis;
 
// Stores the nodes
// at odd distance
vector<int> odd;
 
// Stores the nodes at
// even distance
vector<int> even;
 
// Function to separate and
// store the odd and even
// distant nodes from source
void bfs()
{
    // Source node
    int src = 1;
 
    // Stores the nodes and their
    // respective distances from
    // the source
    queue<pair<int, int> > q;
 
    // Insert the source
    q.push({ src, 0 });
 
    // Mark the source visited
    vis[src] = 1;
 
    while (!q.empty()) {
 
        // Extract a node from the
        // front of the queue
        int node = q.front().first;
        int dist = q.front().second;
        q.pop();
 
        // If distance from source
        // is odd
        if (dist & 1) {
            odd.push_back(node);
        }
 
        // Otherwise
        else {
            even.push_back(node);
        }
 
        // Traverse its neighbors
        for (auto i : graph[node]) {
 
            // Insert its unvisited
            // neighbours into the queue
            if (!vis.count(i)) {
 
                q.push({ i, (dist + 1) });
                vis[i] = 1;
            }
        }
    }
}
 
// Driver Program
int main()
{
    graph[1].push_back(2);
    graph[2].push_back(1);
    graph[2].push_back(3);
    graph[3].push_back(2);
    graph[3].push_back(4);
    graph[4].push_back(3);
    graph[4].push_back(5);
    graph[5].push_back(4);
    graph[5].push_back(6);
    graph[6].push_back(5);
    graph[6].push_back(1);
    graph[1].push_back(6);
 
    bfs();
 
    if (odd.size() < even.size()) {
        for (int i : odd) {
            cout << i << " ";
        }
    }
    else {
        for (int i : even) {
            cout << i << " ";
        }
    }
    return 0;
}

Java

// Java program to implement the
// above approach
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
 
class Pair 
{
    int first, second;
 
    public Pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }
}
 
class GFG{
 
// Stores the graph
static Map<Integer, ArrayList<Integer>> graph = new HashMap<>();
 
// Stores the visited nodes
static Map<Integer, Integer> vis = new HashMap<>();
 
// Stores the nodes
// at odd distance
static ArrayList<Integer> odd = new ArrayList<>();
 
// Stores the nodes at
// even distance
static ArrayList<Integer> even = new ArrayList<>();
 
// Function to separate and
// store the odd and even
// distant nodes from source
static void bfs()
{
     
    // Source node
    int src = 1;
 
    // Stores the nodes and their
    // respective distances from
    // the source
    Queue<Pair> q = new LinkedList<>();
 
    // Insert the source
    q.add(new Pair(src, 0));
 
    // Mark the source visited
    vis.put(src, 1);
 
    while (!q.isEmpty())
    {
         
        // Extract a node from the
        // front of the queue
        int node = q.peek().first;
        int dist = q.peek().second;
        q.poll();
 
        // If distance from source
        // is odd
        if ((dist & 1) != 0) 
        {
            odd.add(node);
        }
 
        // Otherwise
        else
        {
            even.add(node);
        }
 
        // Traverse its neighbors
        for(Integer i : graph.get(node)) 
        {
             
            // Insert its unvisited
            // neighbours into the queue
            if (!vis.containsKey(i))
            {
                q.add(new Pair(i, (dist + 1)));
                vis.put(i, 1);
            }
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    graph.put(1, new ArrayList<>());
    graph.put(2, new ArrayList<>());
    graph.put(3, new ArrayList<>());
    graph.put(4, new ArrayList<>());
    graph.put(5, new ArrayList<>());
    graph.put(6, new ArrayList<>());
    graph.get(1).add(2);
    graph.get(2).add(1);
    graph.get(2).add(3);
    graph.get(3).add(2);
    graph.get(3).add(4);
    graph.get(4).add(3);
    graph.get(4).add(5);
    graph.get(5).add(4);
    graph.get(5).add(6);
    graph.get(6).add(5);
    graph.get(6).add(1);
    graph.get(1).add(6);
 
    bfs();
 
    if (odd.size() < even.size()) 
    {
        for(int i : odd)
        {
            System.out.print(i + " ");
        }
    } 
    else
    {
        for(int i : even)
        {
            System.out.print(i + " ");
        }
    }
}
}
 
// This code is contributed by sanjeev2552

Python3

# Python3 Program to implement the
# above approach
  
# Stores the graph
graph = dict()
  
# Stores the visited nodes
vis = dict()
  
# Stores the nodes
# at odd distance
odd = []
  
# Stores the nodes at
# even distance
even = []
  
# Function to separate and
# store the odd and even
# distant nodes from source
def bfs():
 
    # Source node
    src = 1;
  
    # Stores the nodes and their
    # respective distances from
    # the source
    q = []
  
    # Insert the source
    q.append([ src, 0 ]);
  
    # Mark the source visited
    vis[src] = 1;
  
    while (len(q) != 0):
  
        # Extract a node from the
        # front of the queue
        node = q[0][0]
        dist = q[0][1]
        q.pop(0);
  
        # If distance from source
        # is odd
        if (dist & 1):
            odd.append(node);
  
        # Otherwise
        else:
            even.append(node);
          
        # Traverse its neighbors
        for i in graph[node]:
  
            # Insert its unvisited
            # neighbours into the queue
            if (i not in vis):
  
                q.append([ i, (dist + 1) ]);
                vis[i] = 1;
              
# Driver code
if __name__=='__main__':
 
    graph[1] = [2, 6]
    graph[2] = [1, 3]
    graph[3] = [2, 4]
    graph[4] = [3, 5]
    graph[5] = [4, 6]
    graph[6] = [5, 1]
  
    bfs();
  
    if (len(odd) < len(even)):
        for i in odd:
            print(i, end = ' ')
             
    else:
        for i in even:
            print(i, end = ' ')
             
# This code is contributed by rutvik_56

C#

// C# program to implement the above approach
using System;
using System.Collections.Generic;
 
class Pair {
  public int first, second;
  public Pair(int first, int second)
  {
    this.first = first;
    this.second = second;
  }
}
 
public class GFG {
 
  // Stores the graph
  static Dictionary<int, List<int> > graph
    = new Dictionary<int, List<int> >();
 
  // Stores the visited nodes
  static Dictionary<int, int> vis
    = new Dictionary<int, int>();
 
  // Stores the nodes
  // at odd distance
  static List<int> odd = new List<int>();
 
  // Stores the nodes at
  // even distance
  static List<int> even = new List<int>();
 
  // Function to separate and
  // store the odd and even
  // distant nodes from source
  static void bfs()
  {
    // Source node
    int src = 1;
 
    // Stores the nodes and their
    // respective distances from
    // the source
    Queue<Pair> q = new Queue<Pair>();
 
    // Insert the source
    q.Enqueue(new Pair(src, 0));
 
    // Mark the source visited
    vis[src] = 1;
 
    while (q.Count != 0) {
      // Extract a node from the
      // front of the queue
      int node = q.Peek().first;
      int dist = q.Peek().second;
      q.Dequeue();
 
      // If distance from source
      // is odd
      if ((dist & 1) != 0) {
        odd.Add(node);
      }
 
      // Otherwise
      else {
        even.Add(node);
      }
 
      // Traverse its neighbors
      foreach(int i in graph[node])
      {
        // Insert its unvisited
        // neighbours into the queue
        if (!vis.ContainsKey(i)) {
          q.Enqueue(new Pair(i, (dist + 1)));
          vis[i] = 1;
        }
      }
    }
  }
 
  static public void Main()
  {
 
    // Code
    graph[1] = new List<int>();
    graph[2] = new List<int>();
    graph[3] = new List<int>();
    graph[4] = new List<int>();
    graph[5] = new List<int>();
    graph[6] = new List<int>();
    graph[1].Add(2);
    graph[2].Add(1);
    graph[2].Add(3);
    graph[3].Add(2);
    graph[3].Add(4);
    graph[4].Add(3);
    graph[4].Add(5);
    graph[5].Add(4);
    graph[5].Add(6);
    graph[6].Add(5);
    graph[6].Add(1);
    graph[1].Add(6);
 
    bfs();
 
    if (odd.Count < even.Count) {
      foreach(int i in odd)
      {
        Console.Write(i + " ");
      }
    }
    else {
      foreach(int i in even)
      {
        Console.Write(i + " ");
      }
    }
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

// JavaScript code to implement the above approach
 
// Stores the graph
let graph = new Map();
 
// Stores the visited nodes
let vis = new Map();
 
// Stores the nodes at odd distance
let odd = [];
 
// Stores the nodes at even distance
let even = [];
 
// Function to separate and store the odd and even distant nodes from source
function bfs() {
  // Source node
  let src = 1;
 
  // Stores the nodes and their respective distances from the source
  let q = [];
 
  // Insert the source
  q.push({ first: src, second: 0 });
 
  // Mark the source visited
  vis.set(src, 1);
 
  while (q.length > 0) {
    // Extract a node from the front of the queue
    let node = q[0].first;
    let dist = q[0].second;
    q.shift();
 
    // If distance from source is odd
    if (dist & 1 !== 0) {
      odd.push(node);
    }
    // Otherwise
    else {
      even.push(node);
    }
 
    // Traverse its neighbors
    let neighbors = graph.get(node);
    for (let i of neighbors) {
      // Insert its unvisited neighbors into the queue
      if (!vis.has(i)) {
        q.push({ first: i, second: dist + 1 });
        vis.set(i, 1);
      }
    }
  }
}
 
// Initialize graph
graph.set(1, []);
graph.set(2, []);
graph.set(3, []);
graph.set(4, []);
graph.set(5, []);
graph.set(6, []);
 
graph.get(1).push(2);
graph.get(2).push(1, 3);
graph.get(3).push(2, 4);
graph.get(4).push(3, 5);
graph.get(5).push(4, 6);
graph.get(6).push(5, 1);
 
// Call bfs function
bfs();
 
// Print the result
if (odd.length < even.length) {
      console.log(odd.join(" "));
} else {
      console.log(even.join(" "));
}
 
// This code is contributed by karthik.

Output:

1 3 5

Time Complexity: O(V + E)
Auxiliary Space: O(V)

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 zambiatek!