Find palindromic path of given length K in a complete Binary Weighted Graph | Function to print the left path ; j -> i -> j -> i -> j -> k -> j -> k -> j ; i -> j -> i -> j -> k -> j -> k ; Function to print the right path ; j -> i -> j -> i -> j -> k -> j -> k -> j ; i -> j -> i -> j -> k -> j -> k ; Function to check that if there exists a palindromic path in a binary graoh ; Create adjacency matrix ; If K is odd then print the path directly by choosing node 1 and 2 repeatedly ; If K is even Try to find an edge such that weight of edge i -> j and j -> i is equal ; Same weight edges are found ; Store their indexes ; Print the path ; If nodes i , j having equal weight on edges i -> j and j -> i can not be found then try to find three nodes i , j , k such that weights of edges i -> j and j -> k are equal ; To store edges with weight '0' ; To store edges with weight '1' ; Try to find edges i -> j and j -> k having weight 0 ; Print left Path ; Print centre ; Print right path ; Try to find edges i -> j and j -> k which having weight 1 ; cout << k ; ; Driver Code
const printLeftPath = ( i , j , K ) => { if ( K & 1 ) { for ( let p = 0 ; p < K ; p ++ ) { if ( p & 1 ) { document . write ( ` ${ i } ` ) ; } else { document . write ( ` ${ j } ` ) ; } } } else { for ( let p = 0 ; p < K ; p ++ ) { if ( p & 1 ) { document . write ( ` ${ j } ` ) ; } else { document . write ( ` ${ i } ` ) ; } } } } const printRightPath = ( j , k , K ) => { if ( K & 1 ) { for ( let p = 0 ; p < K ; p ++ ) { if ( p & 1 ) { document . write ( ` ${ K } ` ) ; } else { document . write ( ` ${ j } ` ) ; } } } else { for ( let p = 0 ; p < K ; p ++ ) { if ( p & 1 ) { document . write ( ` ${ K } ` ) ; } else { document . write ( ` ${ j } ` ) ; } } } } const constructPalindromicPath = ( edges , n , K ) => { let adj = new Array ( n + 1 ) . fill ( 0 ) . map ( ( ) => new Array ( n + 1 ) . fill ( 0 ) ) ; for ( let i = 0 ; i < edges . length ; i ++ ) { adj [ edges [ i ] [ 0 ] [ 0 ] ] [ edges [ i ] [ 0 ] [ 1 ] ] = edges [ i ] [ 1 ] ; } if ( K & 1 ) { document . write ( ` ` ) ; for ( let i = 1 ; i <= K + 1 ; i ++ ) { document . write ( ` ${ ( i & 1 ) + 1 } ` ) ; } return ; } let found = 0 ; let idx1 , idx2 ; for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= n ; j ++ ) { if ( i == j ) { continue ; } if ( adj [ i ] [ j ] == adj [ j ] [ i ] ) { found = 1 ; idx1 = i ; idx2 = j ; } } } if ( found ) { document . write ( ` ` ) for ( let i = 1 ; i <= K + 1 ; i ++ ) { if ( i & 1 ) { document . write ( ` ${ idx1 } ` ) ; } else { document . write ( ` ${ idx2 } ` ) ; } } return ; } else { let mp1 = new Array ( n + 1 ) . fill ( [ ] ) ; let mp2 = new Array ( n + 1 ) . fill ( [ ] ) ; for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= n ; j ++ ) { if ( i == j ) { continue ; } if ( adj [ i ] [ j ] == ' ' ) { mp1 [ i ] . push ( j ) ; } else { mp2 [ i ] . push ( j ) ; } } } for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= n ; j ++ ) { if ( j == i ) { continue ; } if ( adj [ i ] [ j ] == ' ' ) { if ( mp1 [ j ] . size ( ) ) { let k = mp1 [ j ] [ 0 ] ; if ( k == i k == j ) { continue ; } document . write ( ` ` ) ; K -= 2 ; K = parseInt ( k / 2 ) ; printLeftPath ( i , j , K ) ; document . write ( ` ${ i } ${ j } ${ k } ` ) ; printRightPath ( j , k , K ) ; return ; } } } } for ( let i = 1 ; i <= n ; i ++ ) { for ( let j = 1 ; j <= n ; j ++ ) { if ( j == i ) { continue ; } if ( adj [ i ] [ j ] == ' ' ) { if ( mp1 [ j ] . length ) { let k = mp1 [ j ] [ 0 ] ; if ( k == i k == j ) { continue ; } document . write ( ` ` ) ; K -= 2 ; K = parseInt ( k / 2 ) ; printLeftPath ( i , j , K ) ; document . write ( ` ${ i } ${ j } ${ k } ` ) ; printRightPath ( j , k , K ) ; return ; } } } } } document . write ( " " ) ; } let N = 3 , K = 4 ; let edges = [ [ [ 1 , 2 ] , ' ' ] , [ [ 1 , 3 ] , ' ' ] , [ [ 2 , 1 ] , ' ' ] , [ [ 2 , 3 ] , ' ' ] , [ [ 3 , 1 ] , ' ' ] , [ [ 3 , 2 ] , ' ' ] ] ; constructPalindromicPath ( edges , N , K ) ;