Construct a graph which does not contain any pair of adjacent nodes with same value

0 0 8 minutes read

Given an array arr[] consisting of N characters, the task is to generate a graph of N nodes and (N – 1) Edges such that each node i is associated with character arr[i] and no two adjacent nodes have the same value. If it is possible to make such a graph, then print “Possible” with the pairs of edges. Otherwise, print “Not Possible”.

Examples:

Input: N = 5, arr[] = {‘a’, ‘b’, ‘a’, ‘b’, ‘c’}
Output: “Possible”
1 – 2
1 – 4
1 – 5
5 – 3
Explanation:
One possible graph that can be constructed to satisfy the given conditions is as follows:

Input: N = 3, arr[] = {‘z’, ‘z’, ‘z’}
Output: “Not Possible”

Approach: To construct a graph such that no adjacent node has the same value, the idea is to check if at least two unique values exist or not. If found to be true, such a graph can be constructed. Follow the steps below:

Check for all the values present at each node and if all the node values are the same, it’s not possible to construct the graph.
If any two values are different, there will always be a way to construct such a graph.
Now, select any two unique values, connect the occurrence of all the other values to 1st unique value except the value itself.
Store indices of occurrence of 1st unique value except for its first occurrence and connect all those indices to the second unique value.
This way there will always be a way to construct such a graph with (N – 1) edges.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function that prints the edges of
// the generated graph
void printConnections(
    vector<pair<int, int> > store,
    vector<int> ind, int ind1)
{
    // First print connections
    // stored in store[]
    for (auto pr : store) {
        cout << pr.first << " "
             << pr.second << "\n";
    }
 
    // Check if there is more than one
    // occurrence of 1st unique element
    if (ind.size() != 0) {
 
        // Print all other occurrence
        // of 1st unique element with
        // second unique element
        for (auto x : ind) {
            cout << ind1 << " "
                 << x + 1 << "\n";
        }
    }
}
 
// Function to construct the graph such
// that the every adjacent nodes have
// different value
void constructGraph(char arr[], int N)
{
    vector<int> ind;
 
    // Stores pair of edges formed
    vector<pair<int, int> > store;
 
    // Stores first unique occurrence
    char x = arr[0];
 
    int count = 0, ind1;
 
    for (int i = 1; i <= N - 1; ++i) {
 
        // Check for the second
        // unique occurrence
        if (arr[i] != x) {
 
            // Store indices of 2nd
            // unique occurrence
            ind1 = i + 1;
 
            // To check if arr has only
            // 1 unique element or not
            count++;
 
            // Store the connections of all
            // unique elements with Node 1
            store.push_back({ 1, i + 1 });
        }
 
        // If value at node (i + 1) is
        // same as value at Node 1 then
        // store its indices
        else {
            ind.push_back(i);
        }
    }
 
    // If count is zero then it's not
    // possible to construct the graph
    if (count == 0) {
        cout << "Not Possible";
    }
 
    // If more than 1 unique
    // element is present
    else {
        cout << "Possible"
             << "\n";
 
        // Print the edges
        printConnections(store, ind, ind1);
    }
}
 
// Driver Code
int main()
{
    int N = 5;
 
    // Given array having node values
    char arr[] = { 'a', 'b', 'a', 'b', 'c' };
 
    // Function Call
    constructGraph(arr, N);
 
    return 0;
}

Java

// Java program for the 
// above approach
import java.util.*;
class GFG{
     
static class pair
{ 
  int first, second; 
  public pair(int first, 
              int second)  
  { 
    this.first = first; 
    this.second = second; 
  }    
} 
 
// Function that prints the edges of
// the generated graph
static void printConnections(Vector<pair > store,
                             Vector<Integer> ind, 
                             int ind1)
{
  // First print connections
  // stored in store[]
  for (pair pr : store) 
  {
    System.out.print(pr.first + " " + 
                     pr.second + "\n");
  }
 
  // Check if there is more than one
  // occurrence of 1st unique element
  if (ind.size() != 0) 
  {
    // Print all other occurrence
    // of 1st unique element with
    // second unique element
    for (int x : ind) 
    {
      System.out.print(ind1 + " " + 
                      (x + 1) + "\n");
    }
  }
}
 
// Function to construct the graph such
// that the every adjacent nodes have
// different value
static void constructGraph(char arr[], 
                           int N)
{
  Vector<Integer> ind = new Vector<>();
 
  // Stores pair of edges formed
  Vector<pair > store = new Vector<>();
 
  // Stores first unique occurrence
  char x = arr[0];
 
  int count = 0;
  int ind1=-1;
 
  for (int i = 1; i <= N - 1; ++i) 
  {
    // Check for the second
    // unique occurrence
    if (arr[i] != x) 
    {
      // Store indices of 2nd
      // unique occurrence
      ind1 = i + 1;
 
      // To check if arr has only
      // 1 unique element or not
      count++;
 
      // Store the connections of all
      // unique elements with Node 1
      store.add(new pair(1, i + 1 ));
    }
 
    // If value at node (i + 1) is
    // same as value at Node 1 then
    // store its indices
    else
    {
      ind.add(i);
    }
  }
 
  // If count is zero then it's not
  // possible to construct the graph
  if (count == 0) 
  {
    System.out.print("Not Possible");
  }
 
  // If more than 1 unique
  // element is present
  else
  {
    System.out.print("Possible" + 
                     "\n");
 
    // Print the edges
    printConnections(store, 
                     ind, ind1);
  }
}
 
// Driver Code
public static void main(String[] args)
{
  int N = 5;
 
  // Given array having 
  // node values
  char arr[] = {'a', 'b', 
                'a', 'b', 'c'};
 
  // Function Call
  constructGraph(arr, N);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 program for the above approach
 
# Function that prints the edges of
# the generated graph
def printConnections(store, ind, ind1):
     
    # First print connections
    # stored in store[]
    for pr in store:
        print(pr[0], pr[1])
 
    # Check if there is more than one
    # occurrence of 1st unique element
    if (len(ind) != 0):
         
        # Print all other occurrence
        # of 1st unique element with
        # second unique element
        for x in ind:
            print(ind1, x + 1)
             
# Function to construct the graph such
# that the every adjacent nodes have
# different value
def constructGraph(arr, N):
     
    ind = []
 
    # Stores pair of edges formed
    store = []
 
    # Stores first unique occurrence
    x = arr[0]
  
    count, ind1 = 0, 0
 
    for i in range(1, N):
         
        # Check for the second
        # unique occurrence
        if (arr[i] != x):
             
            # Store indices of 2nd
            # unique occurrence
            ind1 = i + 1
 
            # To check if arr has only
            # 1 unique element or not
            count += 1
 
            # Store the connections of all
            # unique elements with Node 1
            store.append([1, i + 1])
 
            # If value at node (i + 1) is
            # same as value at Node 1 then
            # store its indices
        else:
            ind.append(i)
 
    # If count is zero then it's not
    # possible to construct the graph
    if count == 0:
        print("Not Possible")
    else:
         
        # If more than 1 unique
        # element is present
        print("Possible")
 
        # Print the edges
        printConnections(store, ind, ind1)
             
# Driver Code
if __name__ == '__main__':
     
    N = 5
 
    # Given array having node values
    arr = [ 'a', 'b', 'a', 'b', 'c' ]
 
    # Function Call
    constructGraph(arr, N)
 
# This code is contributed by mohit kumar 29

C#

// C# program for the 
// above approach
using System;
using System.Collections.Generic;
class GFG{
     
public class pair
{ 
  public int first, 
  second; 
  public pair(int first, 
              int second)  
  { 
    this.first = first; 
    this.second = second; 
  }    
} 
 
// Function that prints the edges of
// the generated graph
static void printConnections(List<pair > store,
                             List<int> ind, 
                             int ind1)
{
  // First print connections
  // stored in store[]
  foreach (pair pr in store) 
  {
    Console.Write(pr.first + " " + 
                  pr.second + "\n");
  }
 
  // Check if there is more than one
  // occurrence of 1st unique element
  if (ind.Count != 0) 
  {
    // Print all other occurrence
    // of 1st unique element with
    // second unique element
    foreach (int x in ind) 
    {
      Console.Write(ind1 + " " + 
                   (x + 1) + "\n");
    }
  }
}
 
// Function to construct the graph such
// that the every adjacent nodes have
// different value
static void constructGraph(char []arr, 
                           int N)
{
  List<int> ind = new List<int>();
 
  // Stores pair of edges formed
  List<pair > store = new List<pair>();
 
  // Stores first unique occurrence
  char x = arr[0];
 
  int count = 0;
  int ind1=-1;
 
  for (int i = 1; i <= N - 1; ++i) 
  {
    // Check for the second
    // unique occurrence
    if (arr[i] != x) 
    {
      // Store indices of 2nd
      // unique occurrence
      ind1 = i + 1;
 
      // To check if arr has only
      // 1 unique element or not
      count++;
 
      // Store the connections of all
      // unique elements with Node 1
      store.Add(new pair(1, i + 1 ));
    }
 
    // If value at node (i + 1) is
    // same as value at Node 1 then
    // store its indices
    else
    {
      ind.Add(i);
    }
  }
 
  // If count is zero then it's not
  // possible to construct the graph
  if (count == 0) 
  {
    Console.Write("Not Possible");
  }
 
  // If more than 1 unique
  // element is present
  else
  {
    Console.Write("Possible" + 
                     "\n");
 
    // Print the edges
    printConnections(store, 
                     ind, ind1);
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  int N = 5;
 
  // Given array having 
  // node values
  char []arr = {'a', 'b', 
                'a', 'b', 'c'};
 
  // Function Call
  constructGraph(arr, N);
}
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for the
// above approach
 
// Function that prints the edges of
// the generated graph
function printConnections(store, ind, ind1)
{
     
    // First print connections
    // stored in store[]
    for(let pr = 0; pr < store.length; pr++)
    {
        document.write(store[pr][0] + " " +
                       store[pr][1] + "<br>");
    }
     
    // Check if there is more than one
    // occurrence of 1st unique element
    if (ind.length != 0)
    {
         
        // Print all other occurrence
        // of 1st unique element with
        // second unique element
        for(let x = 0; x < ind.length; x++)
        {
            document.write(ind1 + " " +
                        (ind[x] + 1) + "<br>");
        }
    }
}
 
// Function to construct the graph such
// that the every adjacent nodes have
// different value
function constructGraph(arr, N)
{
    let ind = [];
     
    // Stores pair of edges formed
    let store = [];
     
    // Stores first unique occurrence
    let x = arr[0];
     
    let count = 0;
    let ind1 = -1;
     
    for(let i = 1; i <= N - 1; ++i)
    {
         
        // Check for the second
        // unique occurrence
        if (arr[i] != x)
        {
             
            // Store indices of 2nd
            // unique occurrence
            ind1 = i + 1;
             
            // To check if arr has only
            // 1 unique element or not
            count++;
             
            // Store the connections of all
            // unique elements with Node 1
            store.push([1, i + 1]);
        }
         
        // If value at node (i + 1) is
        // same as value at Node 1 then
        // store its indices
        else
        {
            ind.push(i);
        }
    }
     
    // If count is zero then it's not
    // possible to construct the graph
    if (count == 0)
    {
        document.write("Not Possible");
    }
     
    // If more than 1 unique
    // element is present
    else
    {
        document.write("Possible" + "<br>");
         
        // Print the edges
        printConnections(store, ind, ind1);
    }
}
 
// Driver Code
let N = 5;
 
// Given array having
// node values
let arr = [ 'a', 'b', 'a', 'b', 'c' ];
 
// Function Call
constructGraph(arr, N);
 
// This code is contributed by unknown2108
 
</script>

Output:

Possible
1 2
1 4
1 5
5 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 zambiatek!