Dada una array arr[] de tamaño N que consta de distintos enteros del rango [0, N – 1] dispuestos en orden aleatorio. También se dan algunos pares donde cada par denota los índices donde se pueden intercambiar los elementos de la array. No hay límite en el número de intercambios permitidos. La tarea es encontrar si es posible organizar la array en orden ascendente utilizando estos intercambios. Si es posible , imprima Sí; de lo contrario, imprima No.
Ejemplos:
Entrada: arr[] = {0, 4, 3, 2, 1, 5}, pairs[][] = {{1, 4}, {2, 3}} Salida: Sí swap(arr[1
] ,
arr [4]) -> array[] = {0, 1, 3, 2, 4, 5}
swap(array[2], array[3]) -> array[] = {0, 1, 2, 3, 4, 5}
Entrada: arr[] = {1, 2, 3, 0, 4}, pairs[][] = {{2, 3}}
Salida: No
Enfoque: el problema dado se puede considerar como un problema gráfico donde N denota el número total de Nodes en el gráfico y cada par de intercambio denota un borde no dirigido en el gráfico. Tenemos que averiguar si es posible convertir la array de entrada en la forma de {0, 1, 2, 3, …, N – 1} .
Llamemos a la array anterior como B. Ahora descubra todos los componentes conectados de ambas arrays y si los elementos difieren en al menos un componente, entonces la respuesta es No ; de lo contrario, la respuesta es Sí .
A continuación se muestra la implementación del enfoque anterior:
CPP
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function that returns true if the array elements
// can be sorted with the given operation
bool canBeSorted(int N, vector<int> a, int P,
vector<pair<int, int> > vp)
{
// To create the adjacency list of the graph
vector<int> v[N];
// Boolean array to mark the visited nodes
bool vis[N] = { false };
// Creating adjacency list for undirected graph
for (int i = 0; i < P; i++) {
v[vp[i].first].push_back(vp[i].second);
v[vp[i].second].push_back(vp[i].first);
}
for (int i = 0; i < N; i++) {
// If not already visited
// then apply BFS
if (!vis[i]) {
queue<int> q;
vector<int> v1;
vector<int> v2;
// Set visited to true
vis[i] = true;
// Push the node to the queue
q.push(i);
// While queue is not empty
while (!q.empty()) {
int u = q.front();
v1.push_back(u);
v2.push_back(a[u]);
q.pop();
// Check all the adjacent nodes
for (auto s : v[u]) {
// If not visited
if (!vis[s]) {
// Set visited to true
vis[s] = true;
q.push(s);
}
}
}
sort(v1.begin(), v1.end());
sort(v2.begin(), v2.end());
// If the connected component does not
// contain same elements then return false
if (v1 != v2)
return false;
}
}
return true;
}
// Driver code
int main()
{
vector<int> a = { 0, 4, 3, 2, 1, 5 };
int n = a.size();
vector<pair<int, int> > vp = { { 1, 4 }, { 2, 3 } };
int p = vp.size();
if (canBeSorted(n, a, p, vp))
cout << "Yes";
else
cout << "No";
return 0;
}
Java
// Java implementation of the approach
import java.io.*;
import java.util.*;
class GFG
{
// Function that returns true if the array elements
// can be sorted with the given operation
static boolean canBeSorted(int N, ArrayList<Integer> a,
int p, ArrayList<ArrayList<Integer>> vp)
{
// To create the adjacency list of the graph
ArrayList<ArrayList<Integer>> v = new ArrayList<ArrayList<Integer>>();
for(int i = 0; i < N; i++)
{
v.add(new ArrayList<Integer>());
}
// Boolean array to mark the visited nodes
boolean[] vis = new boolean[N];
// Creating adjacency list for undirected graph
for (int i = 0; i < p; i++)
{
v.get(vp.get(i).get(0)).add(vp.get(i).get(1));
v.get(vp.get(i).get(1)).add(vp.get(i).get(0));
}
for (int i = 0; i < N; i++)
{
// If not already visited
// then apply BFS
if (!vis[i])
{
Queue<Integer> q = new LinkedList<>();
ArrayList<Integer> v1 = new ArrayList<Integer>();
ArrayList<Integer> v2 = new ArrayList<Integer>();
// Set visited to true
vis[i] = true;
// Push the node to the queue
q.add(i);
// While queue is not empty
while (q.size() > 0)
{
int u = q.poll();
v1.add(u);
v2.add(a.get(u));
// Check all the adjacent nodes
for(int s: v.get(u))
{
// If not visited
if (!vis[s])
{
// Set visited to true
vis[s] = true;
q.add(s);
}
}
}
Collections.sort(v1);
Collections.sort(v2);
// If the connected component does not
// contain same elements then return false
if(!v1.equals(v2))
{
return false;
}
}
}
return true;
}
// Driver code
public static void main (String[] args)
{
ArrayList<Integer> a = new ArrayList<Integer>(Arrays.asList(0, 4, 3, 2, 1, 5));
int n = a.size();
ArrayList<ArrayList<Integer>> vp = new ArrayList<ArrayList<Integer>>();
vp.add(new ArrayList<Integer>(Arrays.asList(1, 4)));
vp.add(new ArrayList<Integer>(Arrays.asList(2, 3)));
int p = vp.size();
if (canBeSorted(n, a, p, vp))
{
System.out.println("Yes");
}
else
{
System.out.println("No");
}
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation of the approach
from collections import deque as queue
# Function that returns true if the array elements
# can be sorted with the given operation
def canBeSorted(N, a, P, vp):
# To create the adjacency list of the graph
v = [[] for i in range(N)]
# Boolean array to mark the visited nodes
vis = [False]*N
# Creating adjacency list for undirected graph
for i in range(P):
v[vp[i][0]].append(vp[i][1])
v[vp[i][1]].append(vp[i][0])
for i in range(N):
# If not already visited
# then apply BFS
if (not vis[i]):
q = queue()
v1 = []
v2 = []
# Set visited to true
vis[i] = True
# Push the node to the queue
q.append(i)
# While queue is not empty
while (len(q) > 0):
u = q.popleft()
v1.append(u)
v2.append(a[u])
# Check all the adjacent nodes
for s in v[u]:
# If not visited
if (not vis[s]):
# Set visited to true
vis[s] = True
q.append(s)
v1 = sorted(v1)
v2 = sorted(v2)
# If the connected component does not
# contain same elements then return false
if (v1 != v2):
return False
return True
# Driver code
if __name__ == '__main__':
a = [0, 4, 3, 2, 1, 5]
n = len(a)
vp = [ [ 1, 4 ], [ 2, 3 ] ]
p = len(vp)
if (canBeSorted(n, a, p, vp)):
print("Yes")
else:
print("No")
# This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript implementation of the approach
// Function that returns true if the array elements
// can be sorted with the given operation
function canBeSorted(N,a,p,vp)
{
// To create the adjacency list of the graph
let v= [];
for(let i = 0; i < N; i++)
{
v.push([]);
}
// Boolean array to mark the visited nodes
let vis = new Array(N);
// Creating adjacency list for undirected graph
for (let i = 0; i < p; i++)
{
v[vp[i][0]].push(vp[i][1]);
v[vp[i][1]].push(vp[i][0]);
}
for (let i = 0; i < N; i++)
{
// If not already visited
// then apply BFS
if (!vis[i])
{
let q = [];
let v1 = [];
let v2 = [];
// Set visited to true
vis[i] = true;
// Push the node to the queue
q.push(i);
// While queue is not empty
while (q.length > 0)
{
let u = q.shift();
v1.push(u);
v2.push(a[u]);
// Check all the adjacent nodes
for(let s=0;s<v[u].length;s++)
{
// If not visited
if (!vis[v[u][s]])
{
// Set visited to true
vis[v[u][s]] = true;
q.push(v[u][s]);
}
}
}
v1.sort(function(c,d){return c-d;});
v2.sort(function(c,d){return c-d;});
// If the connected component does not
// contain same elements then return false
if(v1.toString()!=(v2).toString())
{
return false;
}
}
}
return true;
}
// Driver code
let a = [0, 4, 3, 2, 1, 5];
let n = a.length;
let vp = [];
vp.push([1, 4]);
vp.push([2, 3]);
let p = vp.length;
if (canBeSorted(n, a, p, vp))
{
document.write("Yes");
}
else
{
document.write("No");
}
// This code is contributed by unknown2108
</script>
Producción:
Yes
Complejidad temporal: O(N)
Espacio auxiliar: O(N)