text: Construct an N | C ++ program to implement the above approach ; Keep track of visited nodes ; Function to construct a tree such that there are no two adjacent nodes with the same weight ; If minimum and maximum elements are equal , i . e . array contains one distinct element ; Tree cannot be constructed ; Otherwise ; Tree can be constructed ; Choose weights [ 0 ] as root ; First Node is visited ; Traverse the array ; Otherwise , make an edge ; Mark this node as visited ; Find a weight not same as the root & make edges with that node ; Join non - roots with remaining nodes ; Check if current node ' s ▁ weight ▁ ▁ is ▁ same ▁ as ▁ root ▁ node ' s weight and if it is not visited or not ; Driver Code ; Function Call
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 1e5 + 5 ; int visited [ N ] ; void construct_tree ( int weights [ ] , int n ) { int minimum = * min_element ( weights , weights + n ) ; int maximum = * max_element ( weights , weights + n ) ; if ( minimum == maximum ) { cout << " No " ; return ; } else { cout << " Yes " << endl ; } int root = weights [ 0 ] ; visited [ 1 ] = 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( weights [ i ] != root && visited [ i + 1 ] == 0 ) { cout << 1 << " ▁ " << i + 1 << " ▁ " << endl ; visited [ i + 1 ] = 1 ; } } int notroot = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( weights [ i ] != root ) { notroot = i + 1 ; break ; } } for ( int i = 0 ; i < n ; i ++ ) { if ( weights [ i ] == root && visited [ i + 1 ] == 0 ) { cout << notroot << " ▁ " << i + 1 << endl ; visited [ i + 1 ] = 1 ; } } } int main ( ) { int weights [ ] = { 1 , 2 , 1 , 2 , 5 } ; int N = sizeof ( weights ) / sizeof ( weights [ 0 ] ) ; construct_tree ( weights , N ) ; }