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>
Producción
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