Dado un grafo dirigido completo que tiene N vértices, cuyas aristas pesan ‘1’ o ‘0’, la tarea es encontrar un camino de longitud exactamente K que sea un palíndromo . Escriba “ SÍ ” si es posible y luego la ruta, de lo contrario escriba “ NO ”.
Ejemplo:
Entrada : N = 3, K = 4
aristas[] = {{{1, 2}, ‘1’}, {{1, 3}, ‘1’}, {{2, 1}, ‘1’}, {{2, 3}, ‘1’}, {{3, 1}, ‘0’}, {{3, 2}, ‘0’}}
Salida :
SÍ
2 1 2 1 2
Explicación :El camino seguido es el “1111” que es palíndromo.
Entrada : N = 2, K = 6
aristas[] = { { 1, 2 }, ‘1’ }, { { 2, 1 }, ‘0’ }
Salida: NO
Enfoque : El problema anterior se puede resolver considerando diferentes casos y construyendo las respuestas respectivas. Siga los pasos a continuación para resolver el problema:
- Si K es impar:
- Existe un camino palindrómico en todos los casos si K es impar.
- Se puede construir seleccionando dos Nodes cualesquiera y recorriéndolos K veces, por ejemplo, para K = 5: «00000», «11111», «10101», «01010».
- Si K es par:
- Ahora el problema se puede dividir en dos casos:
- Si existen dos Nodes (i, j) tales que el peso de la arista i->j es igual al peso de la arista j->i. Luego, la respuesta se puede construir recorriéndolos hasta que se alcance la longitud de ruta K.
- De lo contrario, si existen tres Nodes diferentes (i, j, k) tales que el peso de la arista i->j es igual al peso de la arista j->k . Luego, estos tres Nodes se pueden colocar en el centro de la ruta, como …i->j-> i->j->k ->j->k…, para crear un palíndromo de longitud uniforme.
- Ahora el problema se puede dividir en dos casos:
- Escriba la respuesta de acuerdo con la observación anterior.
A continuación se muestra la implementación del enfoque anterior:
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); }
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.
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
Complejidad temporal: O(N*N)
Espacio auxiliar: O(N*N)
Publicación traducida automáticamente
Artículo escrito por kartikmodi y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA