Find palindromic path of given length K in a complete Binary Weighted Graph

Approach

We can solve this problem by considering different cases (for even and odd K) and then finding answers for individual cases. 

Observe here that there always exists a palindromic path when K is odd. Consider two nodes i, j such that i->j has weight 1 and j->i have weight 0. Then we can always construct a palindromic path of any odd length ( i->j->i->j . . .).

In the case of K being even, there may be two situations. First that there exists a pair of nodes i and j such that the edge weight of i->j is equal to j->i. Then we can construct an even length palindromic path by rotating around i and j (i->j->i->j->i…).

Otherwise, if there exists a triplet of nodes i, j, and k such that the edge weight of i->j is equal to j->k. Then we can place these three nodes in the center of two odd-length paths to construct an even-length palindromic path. 

Algorithm

1. Odd K:

a. Print the path by choosing any two nodes repeatedly.

2. Even K:

a. If there exists a pair of nodes i, j such that weight of i->j == j->i, then print i and j repeatedly. 

b. Otherwise if there exists a triplet of nodes (i, j, and k) such that i->j == j->k, then print the path accordingly.

Program

// C++ implementation for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
/* Utility function for printing left part of the palindrome (if it exist) */
void printLeftPath(int i, int j, int K){
    int idx1 = i, idx2 = j;
 
    if(K&1){
        // if K is odd
        // j->i->j->i->j->k->j->k->j
        swap(idx1, idx2);
    }
    // if K is even
    // i->j->i->j->k->j->k
 
    for(int p=0; p<K; p++){
        cout << (p&1 ? idx2 : idx1) << " ";
    }
}
 
/* Utility function for printing right part of the palindrome (if it exist) */
void printRightPath(int j, int k, int K){
    for(int p=0; p<K; p++){
        cout << (p&1 ? k : j) << " ";
    }
    cout<<endl;
}
 
 
/**
 * @brief This function prints the final path (if exist).
 *
 * @param i node
 * @param j node
 * @param k node
 * @param K number of edges in palindromic path.
 */
void printPath(int i, int j, int k, int K){
    cout << "YES" << endl;
    K -= 2;
    K /= 2;
    printLeftPath(i, j, K);
    cout << i << " " << j << " " << k << " ";
    printRightPath(j, k, K);
}
 
/**
 * @brief Function to check
 * that if there is a palindromic path in a binary graph.
 */
void findPalindromicPath(){
    int n;cin>>n; // number of nodes.
    int K;cin>>K; // number of edges in palindromic path.
 
    // Adjacency list of given graph.
    vector<vector<int>> adj(n+1, vector<int>(n+1, -1));
 
    // number of edges will n*(n-1), because given graph
    // will be a complete graph.
    int e = n*(n-1);
 
    // Taking graph input.
    for(int i=0; i<e; i++){
        int u,v,w;
        // nodes are numbered starting from '1'.
        cin >> u >> v >> w;
        adj[u][v] = w;
    }
 
    /**
     * If 'K' is odd, print the path
     * simply by choosing nodes 1 and n repeatedly.
     */
    if(K&1){
        cout << "YES" << endl;
        for(int i=0; i<=K; i++)cout << (i&1 ? n : 1) << " ";
        cout<<endl;
        return;
    }
 
    /**
     * If 'K' is even, we first check if there an edge
     * such that weight of i->j and j->i is equal.
     */
    int idx1 = -1, idx2 = -1;
    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]){
                idx1=i, idx2=j;
                break;
            }
        }
    }
    if(idx1 != -1){
        cout << "YES" << endl;
        for(int i=0; i<=K; i++)cout << (i&1 ? idx1 : idx2) << " ";
        cout<<endl;
        return;
    }
 
    /**
     * If no such edge exists, we try to find
     * three nodes (i, j, k) such that
     * weight of i->j and j->k is equal.
     */
 
    vector<int>edgew0[n+1]; // To store edges with weight '0' .
    vector<int>edgew1[n+1]; // To store edges with weight '1' .
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == 1)edgew1[i].push_back(j);
            else edgew0[i].push_back(j);
        }
    }
 
    /**
     * Check if there exist edges i->j & j->k
     * having weight 1
     */
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == 1 && edgew1[j].size()){
                int k = edgew1[j][0];
                if(k != i && k != j){
                    printPath(i, j, k, K);
                    return;
                }
            }
        }
    }
 
    /**
     * Check if there exist edges i->j & j->k
     * having weight 0
     */
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            if(i == j)continue;
 
            if(adj[i][j] == 0 && edgew0[j].size()){
                int k = edgew0[j][0];
                if(k != i && k != j){
                    printPath(i, j, k, K);
                    return;
                }
            }
        }
    }
 
    cout << "NO" << endl;
}
 
int main(){
    int tt;cin >> tt;
    while(tt--){
        // nodes are numbered starting from '1'.
        findPalindromicPath();
    }
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

INPUT

2
3 4
1 2 1
1 3 1
2 1 1
2 3 1
3 1 0
3 2 0
2 6
1 2 1
2 1 0

OUTPUT

YES
1 2 1 2 1
NO

Time Complexity

The time complexity of the above program is O(N^2). 

Space Complexity

The auxiliary space complexity of the program is O(N^2). 

You can also read about Palindrome Number in Python here.

FAQs

1. What are the applications of DFS?

Applications of DFS include cycle detection, topological ordering, finding strongly connected components of a graph, etc.

2. How to convert a string into an integer using the C++ STL function What are the applications of BFS?

Applications of BFS include finding the shortest path and minimum spanning tree for the unweighted graphs. It is also used for finding all nodes within one connected component. 

3. How to check whether a given string is a palindrome?

We can check if a given string is a palindrome by using the STL reverse function. 

string str = 'naman';
 
string str1 = str;
reverse(str1.begin(), str1.end());
 
if(str == str1)
    cout << "YES" << endl;
else
    cout << "NO" << endl;

You can also try this code with Online C++ Compiler

Run Code

4. How to find all permutations of an array using C++ STL?

We can find all permutations of a string by using STL next_permutation function.

sort(v.begin(), v.end());
 
do{
    cout << str << endl;
    for(auto x: v)cout << x << “ “;
    cout << endl;
} while(next_permutation(v.begin(), v.end()));

You can also try this code with Online C++ Compiler

Run Code

Key Takeaways

Cheers if you reached here!! 

In this blog, we discussed a problem involving palindrome and graphs, Longest Palindromic Subsequence is another problem that you can check out. Graph problems are prevalent in interviews, but they are hard to implement.

Also read, Permutation of string

Yet learning never stops, and there is a lot more to learn. So head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Learning!!