Dada una array de elementos distintos y una lista de secuencias de subsecuencias de la array, la tarea es verificar si la array dada se puede construir de manera única a partir del conjunto dado de subsecuencias.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}, seqs[][] = {{1, 2}, {2, 3}, {3, 4}}
Salida: Sí
Explicaciones: Las secuencias [1 , 2], [2, 3] y [3, 4] pueden reconstruir de forma única
la array original {1, 2, 3, 4}.
Entrada: arr[] = {1, 2, 3, 4}, seqs[][] = {{1, 2}, {2, 3}, {2, 4}}
Salida: No
Explicaciones: Las secuencias [1 , 2], [2, 3] y [2, 4] no pueden reconstruir de forma única
{1, 2, 3, 4}. Hay dos secuencias posibles que se pueden construir a partir de las secuencias dadas:
1) {1, 2, 3, 4}
2) {1, 2, 4, 3}
Enfoque:
para resolver este problema, necesitamos encontrar el ordenamiento topológico de todos los elementos de la array y verificar si existe o no solo un ordenamiento topológico de los elementos, lo que puede confirmarse por la presencia de una sola fuente en cada instante mientras se encuentra el ordenamiento topológico de los elementos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to Check if
// the given array can be constructed
// uniquely from the given set of subsequences
#include <bits/stdc++.h>
using namespace std;
bool canConstruct(vector<int> originalSeq,
vector<vector<int> > sequences)
{
vector<int> sortedOrder;
if (originalSeq.size() <= 0) {
return false;
}
// Count of incoming edges for every vertex
unordered_map<int, int> inDegree;
// Adjacency list graph
unordered_map<int, vector<int> > graph;
for (auto seq : sequences) {
for (int i = 0; i < seq.size(); i++) {
inDegree[seq[i]] = 0;
graph[seq[i]] = vector<int>();
}
}
// Build the graph
for (auto seq : sequences) {
for (int i = 1; i < seq.size(); i++) {
int parent = seq[i - 1], child = seq[i];
graph[parent].push_back(child);
inDegree[child]++;
}
}
// if ordering rules for all the numbers
// are not present
if (inDegree.size() != originalSeq.size()) {
return false;
}
// Find all sources i.e., all vertices
// with 0 in-degrees
queue<int> sources;
for (auto entry : inDegree) {
if (entry.second == 0) {
sources.push(entry.first);
}
}
// For each source, add it to the sortedOrder
// and subtract one from all of in-degrees
// if a child's in-degree becomes zero
// add it to the sources queue
while (!sources.empty()) {
// If there are more than one source
if (sources.size() > 1) {
// Multiple sequences exist
return false;
}
// If the next source is different from the origin
if (originalSeq[sortedOrder.size()] !=
sources.front()) {
return false;
}
int vertex = sources.front();
sources.pop();
sortedOrder.push_back(vertex);
vector<int> children = graph[vertex];
for (auto child : children) {
// Decrement the node's in-degree
inDegree[child]--;
if (inDegree[child] == 0) {
sources.push(child);
}
}
}
// Compare the sizes of sortedOrder
// and the original sequence
return sortedOrder.size() == originalSeq.size();
}
int main(int argc, char* argv[])
{
vector<int> arr = { 1, 2, 6, 7, 3, 5, 4 };
vector<vector<int> > seqs = { { 1, 2, 3 },
{ 7, 3, 5 },
{ 1, 6, 3, 4 },
{ 2, 6, 5, 4 } };
bool result = canConstruct(arr, seqs);
if (result)
cout << "Yes" << endl;
else
cout << "No" << endl;
}
Java
// Java program to Check if
// the given array can be constructed
// uniquely from the given set of subsequences
import java.io.*;
import java.util.*;
class GFG {
static boolean canConstruct(int[] originalSeq,
int[][] sequences)
{
List<Integer> sortedOrder
= new ArrayList<Integer>();
if (originalSeq.length <= 0) {
return false;
}
// Count of incoming edges for every vertex
Map<Integer, Integer> inDegree
= new HashMap<Integer, Integer>();
// Adjacency list graph
Map<Integer, ArrayList<Integer> > graph
= new HashMap<Integer, ArrayList<Integer> >();
for (int[] seq : sequences)
{
for (int i = 0; i < seq.length; i++)
{
inDegree.put(seq[i], 0);
graph.put(seq[i], new ArrayList<Integer>());
}
}
// Build the graph
for (int[] seq : sequences)
{
for (int i = 1; i < seq.length; i++)
{
int parent = seq[i - 1], child = seq[i];
graph.get(parent).add(child);
inDegree.put(child,
inDegree.get(child) + 1);
}
}
// if ordering rules for all the numbers
// are not present
if (inDegree.size() != originalSeq.length)
{
return false;
}
// Find all sources i.e., all vertices
// with 0 in-degrees
List<Integer> sources = new ArrayList<Integer>();
for (Map.Entry<Integer, Integer> entry :
inDegree.entrySet())
{
if (entry.getValue() == 0)
{
sources.add(entry.getKey());
}
}
// For each source, add it to the sortedOrder
// and subtract one from all of in-degrees
// if a child's in-degree becomes zero
// add it to the sources queue
while (!sources.isEmpty())
{
// If there are more than one source
if (sources.size() > 1)
{
// Multiple sequences exist
return false;
}
// If the next source is different from the
// origin
if (originalSeq[sortedOrder.size()]
!= sources.get(0))
{
return false;
}
int vertex = sources.get(0);
sources.remove(0);
sortedOrder.add(vertex);
List<Integer> children = graph.get(vertex);
for (int child : children)
{
// Decrement the node's in-degree
inDegree.put(child,
inDegree.get(child) - 1);
if (inDegree.get(child) == 0)
{
sources.add(child);
}
}
}
// Compare the sizes of sortedOrder
// and the original sequence
return sortedOrder.size() == originalSeq.length;
}
// Driver code
public static void main(String[] args)
{
int[] arr = { 1, 2, 6, 7, 3, 5, 4 };
int[][] seqs = { { 1, 2, 3 },
{ 7, 3, 5 },
{ 1, 6, 3, 4 },
{ 2, 6, 5, 4 } };
boolean result = canConstruct(arr, seqs);
if (result)
System.out.println("Yes");
else
System.out.println("No");
}
}
// This code is contributed by jitin
Python3
# Python 3 program to Check if
# the given array can be constructed
# uniquely from the given set of subsequences
def canConstruct(originalSeq, sequences):
sortedOrder = []
if (len(originalSeq) <= 0):
return False
# Count of incoming edges for every vertex
inDegree = {i : 0 for i in range(100)}
# Adjacency list graph
graph = {i : [] for i in range(100)}
for seq in sequences:
for i in range(len(seq)):
inDegree[seq[i]] = 0
graph[seq[i]] = []
# Build the graph
for seq in sequences:
for i in range(1, len(seq)):
parent = seq[i - 1]
child = seq[i]
graph[parent].append(child)
inDegree[child] += 1
# If ordering rules for all the numbers
# are not present
if (len(inDegree) != len(originalSeq)):
return False
# Find all sources i.e., all vertices
# with 0 in-degrees
sources = []
for entry in inDegree:
if (entry[1] == 0):
sources.append(entry[0])
# For each source, add it to the sortedOrder
# and subtract one from all of in-degrees
# if a child's in-degree becomes zero
# add it to the sources queue
while (len(sources) > 0):
# If there are more than one source
if (len(sources) > 1):
# Multiple sequences exist
return False
# If the next source is different from the origin
if (originalSeq[len(sortedOrder)] != sources[0]):
return False
vertex = sources[0]
sources.remove(sources[0])
sortedOrder.append(vertex)
children = graph[vertex]
for child in children:
# Decrement the node's in-degree
inDegree[child] -= 1
if (inDegree[child] == 0):
sources.append(child)
# Compare the sizes of sortedOrder
# and the original sequence
return len(sortedOrder) == len(originalSeq)
if __name__ == '__main__':
arr = [ 1, 2, 6, 7, 3, 5, 4 ]
seqs = [[ 1, 2, 3 ],
[ 7, 3, 5 ],
[ 1, 6, 3, 4 ],
[ 2, 6, 5, 4 ]]
result = canConstruct(arr, seqs)
if (result):
print("Yes")
else:
print("No")
# This code is contributed by Bhupendra_Singh
Javascript
<script>
// JavaScript program to Check if
// the given array can be constructed
// uniquely from the given set of subsequences
function canConstruct(originalSeq, sequences)
{
let sortedOrder = [];
if (originalSeq.length <= 0) {
return false;
}
// Count of incoming edges for every vertex
let inDegree = new Map();
// Adjacency list graph
let graph = new Array(100).fill(0).map(()=>[]);
for (let seq of sequences) {
for (let i = 0; i < seq.length; i++) {
inDegree.set(seq[i] , 0);
graph[seq[i]] = [];
}
}
// Build the graph
for (let seq of sequences) {
for (let i = 1; i < seq.length; i++) {
let parent = seq[i - 1], child = seq[i];
graph[parent].push(child);
if(inDegree.has(child))
inDegree.set(child,inDegree.get(child)+1);
else
inDegree.set(child,1);
}
}
// if ordering rules for all the numbers
// are not present
if (inDegree.length != originalSeq.length) {
return false;
}
// Find all sources i.e., all vertices
// with 0 in-degrees
let sources = [];
for (let [entry,res] of inDegree) {
if (res== 0) {
sources.push(entry);
}
}
// For each source, add it to the sortedOrder
// and subtract one from all of in-degrees
// if a child's in-degree becomes zero
// add it to the sources queue
while (sources.length > 0) {
// If there are more than one source
if (sources.length > 1) {
// Multiple sequences exist
return false;
}
// If the next source is different from the origin
if (originalSeq[sortedOrder.length] !=
sources[0]) {
return false;
}
let vertex = sources.shift();
sortedOrder.push(vertex);
let children = graph[vertex];
for (let child of children) {
// Decrement the node's in-degree
if(inDegree.has(child)){
inDegree.set(child,inDegree.get(child)-1);
}
if (inDegree.get(child) == 0) {
sources.push(child);
}
}
}
// Compare the sizes of sortedOrder
// and the original sequence
return sortedOrder.length == originalSeq.length;
}
// driver code
let arr = [ 1, 2, 6, 7, 3, 5, 4 ];
let seqs = [ [ 1, 2, 3],
[ 7, 3, 5],
[ 1, 6, 3, 4],
[ 2, 6, 5, 4]];
let result = canConstruct(arr, seqs);
if (result)
document.write("Yes","</br>");
else
document.write("No","</br>");
// This code is contributed by shinjanpatra
</script>
Producción:
No
Complejidad temporal:
La complejidad temporal del algoritmo anterior será O(N+E), donde ‘N’ es el número de elementos y ‘E’ es el número total de reglas. Dado que, como mucho, cada par de números puede darnos una regla, podemos concluir que el límite superior de las reglas es O(M) donde ‘M’ es el conteo de números en todas las secuencias. Entonces, podemos decir que la complejidad temporal de nuestro algoritmo es O(N + M).
Espacio Auxiliar : O(N+ M), ya que estamos almacenando todas las reglas posibles para cada elemento.