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 graphvoid 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 valuevoid 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 Codeint 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 approachimport 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 graphstatic 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 valuestatic 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 Codepublic 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 graphdef 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 valuedef 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 Codeif __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 approachusing 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 graphstatic 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 valuestatic 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 Codepublic 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 graphfunction 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 valuefunction 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 Codelet N = 5;// Given array having// node valueslet arr = [ 'a', 'b', 'a', 'b', 'c' ];// Function CallconstructGraph(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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
