**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;
}
```

**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;
```

**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()));
```

**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!!