Find palindromic path of given length K in a complete Binary Weighted Graph
Given a complete directed graph having N vertices, whose edges weighs β1β or β0β, the task is to find a path of length exactly K which is a palindrome. Print βYESβ if possible and then the path, otherwise print βNOβ.
Example:
Input: N = 3, K = 4
edges[] = {{{1, 2}, β1β}, {{1, 3}, β1β}, {{2, 1}, β1β}, {{2, 3}, β1β}, {{3, 1}, β0β}, {{3, 2}, β0β}}
Output:
YES
2 1 2 1 2
Explanation:The path followed is β1111β which is palindrome.
Input: N = 2, K = 6
edges[] = { { 1, 2 }, β1β }, { { 2, 1 }, β0β }
Output: NO
Approach: The above problem can be solved by considering different cases and constructing the respective answers. Follow the below steps to solve the problem:
- If K is odd:
- There exists a palindromic path in every case if K is odd.
- It can be constructed by selecting any two nodes and looping through them K times, For example, for K = 5: β00000β, β11111β, β10101β, β01010β.
- If K is even:
- Now the problem can be divided into two cases:
- If Two nodes (i, j) exists such that the weight of edge i->j is equal to the weight of edge j->i. Then the answer can be constructed by looping through them until path length K is achieved.
- Otherwise, if there exist three different nodes (i, j, k) such that the weight of edge i->j is equal to the weight of edge j->k. Then these three nodes can be placed in the centre of the path, like β¦i->j->i->j->k->j->kβ¦, to create an even length palindrome.
- Now the problem can be divided into two cases:
- Print the answer according to the above observation.
Below is the implementation of the above approach:
C++
// C++ implementation for the above approach #include <bits/stdc++.h> using namespace std; // Function to print the left path void printLeftPath( int i, int j, int K) { if (K & 1) { // j->i->j->i->j->k->j->k->j for ( int p = 0; p < K; p++) { if (p & 1) { cout << i << " " ; } else { cout << j << " " ; } } } else { // i->j->i->j->k->j->k for ( int p = 0; p < K; p++) { if (p & 1) { cout << j << " " ; } else { cout << i << " " ; } } } } // Function to print the right path void printRightPath( int j, int k, int K) { if (K & 1) { // j->i->j->i->j->k->j->k->j for ( int p = 0; p < K; p++) { if (p & 1) { cout << k << " " ; } else { cout << j << " " ; } } } else { // i->j->i->j->k->j->k for ( int p = 0; p < K; p++) { if (p & 1) { cout << k << " " ; } else { cout << j << " " ; } } } } // Function to check that // if there exists a palindromic path // in a binary graph void constructPalindromicPath( vector<pair<pair< int , int >, char > > edges, int n, int K) { // Create adjacency matrix vector<vector< char > > adj( n + 1, vector< char >(n + 1)); for ( int i = 0; i < edges.size(); i++) { adj[edges[i] .first.first][edges[i] .first.second] = edges[i].second; } // If K is odd then // print the path directly by // choosing node 1 and 2 repeatedly if (K & 1) { cout << "YES" << endl; for ( int i = 1; i <= K + 1; i++) { cout << (i & 1) + 1 << " " ; } return ; } // If K is even // Try to find an edge such that weight of // edge i->j and j->i is equal bool found = 0; int idx1, idx2; for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (i == j) { continue ; } if (adj[i][j] == adj[j][i]) { // Same weight edges are found found = 1; // Store their indexes idx1 = i, idx2 = j; } } } if (found) { // Print the path cout << "YES" << endl; for ( int i = 1; i <= K + 1; i++) { if (i & 1) { cout << idx1 << " " ; } else { cout << idx2 << " " ; } } return ; } // 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 else { // To store edges with weight '0' vector< int > mp1[n + 1]; // To store edges with weight '1' vector< int > mp2[n + 1]; for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (i == j) { continue ; } if (adj[i][j] == '0' ) { mp1[i].push_back(j); } else { mp2[i].push_back(j); } } } // Try to find edges i->j and // j->k having weight 0 for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (j == i) { continue ; } if (adj[i][j] == '0' ) { if (mp1[j].size()) { int k = mp1[j][0]; if (k == i || k == j) { continue ; } cout << "YES" << endl; K -= 2; K /= 2; // Print left Path printLeftPath(i, j, K); // Print centre cout << i << " " << j << " " << k << " " ; // Print right path printRightPath(j, k, K); return ; } } } } // Try to find edges i->j // and j->k which having // weight 1 for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (j == i) { continue ; } if (adj[i][j] == '1' ) { if (mp1[j].size()) { int k = mp1[j][0]; // cout<<k; if (k == i || k == j) { continue ; } cout << "YES" << endl; K -= 2; K /= 2; printLeftPath(i, j, K); cout << i << " " << j << " " << k << " " ; printRightPath(j, k, K); return ; } } } } } cout << "NO" ; } // Driver Code int main() { int N = 3, K = 4; vector<pair<pair< int , int >, char > > edges = { { { 1, 2 }, '1' }, { { 1, 3 }, '1' }, { { 2, 1 }, '1' }, { { 2, 3 }, '1' }, { { 3, 1 }, '0' }, { { 3, 2 }, '0' } }; constructPalindromicPath(edges, N, K); } |
Java
import java.util.ArrayList; import java.util.List; public class Main { // Function to print the left path static void printLeftPath( int i, int j, int K) { if ((K & 1 ) == 1 ) { // j->i->j->i->j->k->j->k->j for ( int p = 0 ; p < K; p++) { if ((p & 1 ) == 1 ) { System.out.print(i + " " ); } else { System.out.print(j + " " ); } } } else { // i->j->i->j->k->j->k for ( int p = 0 ; p < K; p++) { if ((p & 1 ) == 1 ) { System.out.print(j + " " ); } else { System.out.print(i + " " ); } } } } // Function to print the right path static void printRightPath( int j, int k, int K) { if ((K & 1 ) == 1 ) { // j->i->j->i->j->k->j->k->j for ( int p = 0 ; p < K; p++) { if ((p & 1 ) == 1 ) { System.out.print(k + " " ); } else { System.out.print(j + " " ); } } } else { // i->j->i->j->k->j->k for ( int p = 0 ; p < K; p++) { if ((p & 1 ) == 1 ) { System.out.print(k + " " ); } else { System.out.print(j + " " ); } } } } // Function to check if there exists a palindromic path in a binary graph static void constructPalindromicPath(List<Pair<Pair<Integer, Integer>, Character>> edges, int n, int K) { // Create adjacency matrix char [][] adj = new char [n + 1 ][n + 1 ]; for (Pair<Pair<Integer, Integer>, Character> edge : edges) { int i = edge.getKey().getKey(); int j = edge.getKey().getValue(); char weight = edge.getValue(); adj[i][j] = weight; } // If K is odd, print the path directly by choosing node 1 and 2 repeatedly if ((K & 1 ) == 1 ) { System.out.println( "YES" ); for ( int i = 0 ; i <= K; i++) { System.out.print((i & 1 ) + 1 + " " ); } return ; } // If K is even // Try to find an edge such that the weight of edge i->j and j->i is equal boolean found = false ; int idx1 = 0 , idx2 = 0 ; for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= n; j++) { if (i != j && adj[i][j] == adj[j][i]) { // Same weight edges are found found = true ; idx1 = i; idx2 = j; break ; } } if (found) break ; } if (found) { // Print the path System.out.println( "YES" ); for ( int i = 0 ; i <= K; i++) { System.out.print((i & 1 ) == 1 ? idx1 + " " : idx2 + " " ); } return ; } // 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 else { List<Integer>[] mp1 = new ArrayList[n + 1 ]; List<Integer>[] mp2 = new ArrayList[n + 1 ]; for ( int i = 1 ; i <= n; i++) { mp1[i] = new ArrayList<>(); mp2[i] = new ArrayList<>(); for ( int j = 1 ; j <= n; j++) { if (i != j) { if (adj[i][j] == '0' ) { mp1[i].add(j); } else { mp2[i].add(j); } } } } for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= n; j++) { if (i != j && adj[i][j] == '0' ) { if (!mp1[j].isEmpty()) { int k = mp1[j].get( 0 ); if (k != i && k != j) { System.out.println( "YES" ); K -= 2 ; K /= 2 ; printLeftPath(i, j, K); System.out.print(i + " " + j + " " + k + " " ); printRightPath(j, k, K); return ; } } } } } for ( int i = 1 ; i <= n; i++) { for ( int j = 1 ; j <= n; j++) { if (i != j && adj[i][j] == '1' ) { if (!mp1[j].isEmpty()) { int k = mp1[j].get( 0 ); if (k != i && k != j) { System.out.println( "YES" ); K -= 2 ; K /= 2 ; printLeftPath(i, j, K); System.out.print(i + " " + j + " " + k + " " ); printRightPath(j, k, K); return ; } } } } } } System.out.println( "NO" ); } // Driver code public static void main(String[] args) { int N = 3 , K = 4 ; List<Pair<Pair<Integer, Integer>, Character>> edges = new ArrayList<>(); edges.add( new Pair<>( new Pair<>( 1 , 2 ), '1' )); edges.add( new Pair<>( new Pair<>( 1 , 3 ), '1' )); edges.add( new Pair<>( new Pair<>( 2 , 1 ), '1' )); edges.add( new Pair<>( new Pair<>( 2 , 3 ), '1' )); edges.add( new Pair<>( new Pair<>( 3 , 1 ), '0' )); edges.add( new Pair<>( new Pair<>( 3 , 2 ), '0' )); constructPalindromicPath(edges, N, K); } // Utility Pair class static class Pair<K, V> { private K key; private V value; Pair(K key, V value) { this .key = key; this .value = value; } public K getKey() { return key; } public V getValue() { return value; } } } |
Python3
# Python implementation for the above approach # Function to print the left path def printLeftPath(i, j, K): if (K & 1 ): # j->i->j->i->j->k->j->k->j for p in range ( 0 , K): if (p & 1 ): print (i, end = " " ) else : print (j, end = " " ) else : # i->j->i->j->k->j->k for p in range (K): if (p & 1 ): print (j, end = " " ) else : print (i, end = " " ) # Function to print the right path def printRightPath(j, k, K): if (K & 1 ): # j->i->j->i->j->k->j->k->j for p in range (K): if (p & 1 ): print (K, end = " " ) else : print (j, end = " " ) else : # i->j->i->j->k->j->k for p in range (K): if (p & 1 ): print (K, end = " " ) else : print (j, end = " " ) # Function to check that # if there exists a palindromic path # in a binary graph def constructPalindromicPath(edges, n, K): # Create adjacency matrix adj = [[ 0 for i in range (n + 1 )] for i in range (n + 1 )] for i in range ( len (edges)): adj[edges[i][ 0 ][ 0 ]][edges[i][ 0 ][ 1 ]] = edges[i][ 1 ] # If K is odd then # print the path directly by # choosing node 1 and 2 repeatedly if (K & 1 ): print ( "YES" ) for i in range ( 1 , K + 2 ): print ((i & 1 ) + 1 , end = " " ) return # If K is even # Try to find an edge such that weight of # edge i->j and j->i is equal found = 0 idx1 = None idx2 = None for i in range ( 1 , n + 1 ): for j in range ( 1 , n + 1 ): if (i = = j): continue if (adj[i][j] = = adj[j][i]): # Same weight edges are found found = 1 # Store their indexes idx1 = i idx2 = j if (found): # Print the path print ( "YES" ) for i in range ( 1 , K + 2 ): if (i & 1 ): print (idx1, end = " " ) else : print (idx2, end = " " ) return # 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 else : # To store edges with weight '0' mp1 = [[] for i in range * (n + 1 )] # To store edges with weight '1' mp2 = [[] for i in range (n + 1 )] for i in range ( 1 , n + 1 ): for j in range ( 1 , n + 1 ): if (i = = j): continue if (adj[i][j] = = '0' ): mp1[i].push(j) else : mp2[i].push(j) # Try to find edges i->j and # j->k having weight 0 for i in range ( 1 , n + 1 ): for j in range ( 1 , n + 1 ): if (j = = i): continue if (adj[i][j] = = '0' ): if ( len (mp1[j])): k = mp1[j][ 0 ] if (k = = i or k = = j): continue print ( "YES" ) K - = 2 K = k / / 2 # Print left Path printLeftPath(i, j, K) # Print centre print (f "{i} {j} {k}" ) # Print right path printRightPath(j, k, K) return # Try to find edges i->j # and j->k which having # weight 1 for i in range ( 1 , n + 1 ): for j in range ( 1 , n + 1 ): if (j = = i): continue if (adj[i][j] = = '1' ): if ( len (mp1[j])): k = mp1[j][ 0 ] # cout<<k; if (k = = i or k = = j): continue print ( "YES" ) K - = 2 K = k / / 2 printLeftPath(i, j, K) print (f "{i} {j} {k}" ) printRightPath(j, k, K) return print ( "NO" ) # Driver Code N = 3 K = 4 edges = [[[ 1 , 2 ], '1' ], [[ 1 , 3 ], '1' ], [[ 2 , 1 ], '1' ], [[ 2 , 3 ], '1' ], [[ 3 , 1 ], '0' ], [[ 3 , 2 ], '0' ]] constructPalindromicPath(edges, N, K) # This code is contributed by gfgking. |
C#
using System; using System.Collections.Generic; class Program { // Class to represent a triplet (three integers) class Triplet { public int First { get ; set ; } public int Second { get ; set ; } public char Third { get ; set ; } public Triplet( int first, int second, char third) { First = first; Second = second; Third = third; } } // Function to print the left path static void PrintLeftPath( int i, int j, int K) { if ((K & 1) == 1) { // j->i->j->i->j->k->j->k->j for ( int p = 0; p < K; p++) { Console.Write((p & 1) == 1 ? $ "{i} " : $ "{j} " ); } } else { // i->j->i->j->k->j->k for ( int p = 0; p < K; p++) { Console.Write((p & 1) == 1 ? $ "{j} " : $ "{i} " ); } } } // Function to print the right path static void PrintRightPath( int j, int k, int K) { if ((K & 1) == 1) { // j->i->j->i->j->k->j->k->j for ( int p = 0; p < K; p++) { Console.Write((p & 1) == 1 ? $ "{k} " : $ "{j} " ); } } else { // i->j->i->j->k->j->k for ( int p = 0; p < K; p++) { Console.Write((p & 1) == 1 ? $ "{k} " : $ "{j} " ); } } } // Function to check if there exists a palindromic path in a binary graph static void ConstructPalindromicPath(List<Triplet> edges, int n, int K) { // Create adjacency matrix char [][] adj = new char [n + 1][]; for ( int i = 0; i <= n; i++) { adj[i] = new char [n + 1]; } foreach ( var edge in edges) { adj[edge.First][edge.Second] = edge.Third; } // If K is odd then print the path directly by choosing node 1 and 2 repeatedly if ((K & 1) == 1) { Console.WriteLine( "YES" ); for ( int i = 1; i <= K + 1; i++) { Console.Write(((i & 1) == 1) ? $ "{1} " : $ "{2} " ); } return ; } // If K is even, try to find an edge such that the weight of edge i->j and j->i is equal bool found = false ; int idx1 = 0, idx2 = 0; for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (i == j) { continue ; } if (adj[i][j] == adj[j][i]) { // Same weight edges are found found = true ; // Store their indexes idx1 = i; idx2 = j; } } } if (found) { // Print the path Console.WriteLine( "YES" ); for ( int i = 1; i <= K + 1; i++) { Console.Write(((i & 1) == 1) ? $ "{idx1} " : $ "{idx2} " ); } return ; } // 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 else { // To store edges with weight '0' List< int >[] mp1 = new List< int >[n + 1]; // To store edges with weight '1' List< int >[] mp2 = new List< int >[n + 1]; for ( int i = 1; i <= n; i++) { mp1[i] = new List< int >(); mp2[i] = new List< int >(); for ( int j = 1; j <= n; j++) { if (i == j) { continue ; } if (adj[i][j] == '0' ) { mp1[i].Add(j); } else { mp2[i].Add(j); } } } // Try to find edges i->j and j->k having weight 0 for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (j == i) { continue ; } if (adj[i][j] == '0' ) { if (mp1[j].Count > 0) { int k = mp1[j][0]; if (k == i || k == j) { continue ; } Console.WriteLine( "YES" ); K -= 2; K /= 2; // Print left Path PrintLeftPath(i, j, K); // Print center Console.Write($ "{i} {j} {k} " ); // Print right path PrintRightPath(j, k, K); return ; } } } } // Try to find edges i->j and j->k having weight 1 for ( int i = 1; i <= n; i++) { for ( int j = 1; j <= n; j++) { if (j == i) { continue ; } if (adj[i][j] == '1' ) { if (mp1[j].Count > 0) { int k = mp1[j][0]; if (k == i || k == j) { continue ; } Console.WriteLine( "YES" ); K -= 2; K /= 2; PrintLeftPath(i, j, K); Console.Write($ "{i} {j} {k} " ); PrintRightPath(j, k, K); return ; } } } } } Console.WriteLine( "NO" ); } // Driver Code static void Main() { int N = 3, K = 4; List<Triplet> edges = new List<Triplet> { new Triplet(1, 2, '1' ), new Triplet(1, 3, '1' ), new Triplet(2, 1, '1' ), new Triplet(2, 3, '1' ), new Triplet(3, 1, '0' ), new Triplet(3, 2, '0' ) }; ConstructPalindromicPath(edges, N, K); } } |
Javascript
<script> // JavaScript implementation for the above approach // Function to print the left path const printLeftPath = (i, j, K) => { if (K & 1) { // j->i->j->i->j->k->j->k->j for (let p = 0; p < K; p++) { if (p & 1) { document.write(`${i} `); } else { document.write(`${j} `); } } } else { // i->j->i->j->k->j->k for (let p = 0; p < K; p++) { if (p & 1) { document.write(`${j} `); } else { document.write(`${i} `); } } } } // Function to print the right path const printRightPath = (j, k, K) => { if (K & 1) { // j->i->j->i->j->k->j->k->j for (let p = 0; p < K; p++) { if (p & 1) { document.write(`${K} `); } else { document.write(`${j} `); } } } else { // i->j->i->j->k->j->k for (let p = 0; p < K; p++) { if (p & 1) { document.write(`${K} `); } else { document.write(`${j} `); } } } } // Function to check that // if there exists a palindromic path // in a binary graph const constructPalindromicPath = (edges, n, K) => { // Create adjacency matrix 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 is odd then // print the path directly by // choosing node 1 and 2 repeatedly if (K & 1) { document.write(`YES<br/>`); for (let i = 1; i <= K + 1; i++) { document.write(`${(i & 1) + 1} `); } return ; } // If K is even // Try to find an edge such that weight of // edge i->j and j->i is equal 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]) { // Same weight edges are found found = 1; // Store their indexes idx1 = i; idx2 = j; } } } if (found) { // Print the path document.write(`YES<br/>`) for (let i = 1; i <= K + 1; i++) { if (i & 1) { document.write(`${idx1} `); } else { document.write(`${idx2} `); } } return ; } // 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 else { // To store edges with weight '0' let mp1 = new Array(n + 1).fill([]); // To store edges with weight '1' 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] == '0' ) { mp1[i].push(j); } else { mp2[i].push(j); } } } // Try to find edges i->j and // j->k having weight 0 for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { if (j == i) { continue ; } if (adj[i][j] == '0' ) { if (mp1[j].size()) { let k = mp1[j][0]; if (k == i || k == j) { continue ; } document.write(`YES<br/>`); K -= 2; K = parseInt(k / 2); // Print left Path printLeftPath(i, j, K); // Print centre document.write(`${i} ${j} ${k} `); // Print right path printRightPath(j, k, K); return ; } } } } // Try to find edges i->j // and j->k which having // weight 1 for (let i = 1; i <= n; i++) { for (let j = 1; j <= n; j++) { if (j == i) { continue ; } if (adj[i][j] == '1' ) { if (mp1[j].length) { let k = mp1[j][0]; // cout<<k; if (k == i || k == j) { continue ; } document.write(`YES<br/>`); K -= 2; K = parseInt(k / 2); printLeftPath(i, j, K); document.write(`${i} ${j} ${k} `); printRightPath(j, k, K); return ; } } } } } document.write( "NO" ); } // Driver Code let N = 3, K = 4; let edges = [[[1, 2], '1' ], [[1, 3], '1' ], [[2, 1], '1' ], [[2, 3], '1' ], [[3, 1], '0' ], [[3, 2], '0' ]]; constructPalindromicPath(edges, N, K); // This code is contributed by rakeshsahni. </script> |
YES 2 1 2 1 2
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Contact Us