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