Dada una array 2D arr[][] de tamaño N*M que denota N arrays, cada una de tamaño M . La tarea es verificar si todas estas arrays tienen una supersecuencia común única.
Ejemplos:
Entrada : N = 2, M = 2, arr[][] = { { 1, 2 }, {1, 3 } }
Salida : Falso
Explicación : Hay dos supersecuencias posibles: {1, 3, 2 } y {1 , 2, 3}.Entrada : N = 3, M = 2, arr[][] = { { 1, 2 }, {1, 3}, {2, 3 } }
Salida : Verdadero
Explicación : { 1, 2, 3 } es el único supersecuencia común más corta de {1, 2}, {1, 3} y {2, 3}.
Enfoque : la idea es utilizar la clasificación topológica . Siga los pasos que se mencionan a continuación para resolver el problema:
- Representar las secuencias en ‘ arr[][] ‘ mediante un gráfico dirigido y encontrar su orden de clasificación topológico .
- Si sólo hay un orden de clasificación topológico , entonces se puede decir que sólo hay una supersecuencia común más corta .
- De lo contrario, devuelve falso.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check unique
// shortest common supersequence
bool shortestSuperSeq(vector<vector<int> >& arr,
int N, int M)
{
// Initializing map to store
// edges and indegree of vertices
unordered_map<int, vector<int> > adj;
unordered_map<int, int> indegree;
// Initializing all keys of map
// with values of sequences in arr
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int node = arr[i][j];
adj[node] = {};
indegree[node] = 0;
}
}
// For every sequence in arr
// calculate indegree and edges.
for (auto seq : arr) {
for (int i = 1; i < M; i++) {
adj[seq[i - 1]].push_back(seq[i]);
indegree[seq[i]]++;
}
}
// Vector to store
// topologically sorted order.
vector<int> res;
queue<int> q;
// Push vertices with 0 indegree in queue
for (auto itr : indegree) {
if (itr.second == 0) {
q.push(itr.first);
}
}
while (!q.empty()) {
int size = q.size();
// If size of q > 1, this means
// more than one choices,
// so no unique common supersequence
// can be formed.
if (size != 1)
return false;
int node = q.front();
// Add node to topological sort order
res.push_back(node);
q.pop();
// Decrement indegree of all
// the vertices connected to node
for (int i = 0; i < adj[node].size();
i++) {
int connected_node = adj[node][i];
// Push vertices with 0 indegree
// to queue
if ((--indegree[connected_node])
== 0) {
q.push(connected_node);
}
}
}
// If indegree of any vertices is not 0,
// return false.
for (auto itr : indegree) {
if (itr.second != 0)
return false;
}
return true;
}
// Driver Code
int main()
{
vector<vector<int> > arr = { { 1, 2 },
{ 1, 3 } };
int N = arr.size(), M = arr[0].size();
if (shortestSuperSeq(arr, N, M))
cout << "True\n";
else
cout << "False\n";
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG {
// Function to check unique
// shortest common supersequence
public static boolean
shortestSuperSeq(ArrayList<ArrayList<Integer> > arr,
int N, int M)
{
// Initializing map to store
// edges and indegree of vertices
HashMap<Integer, ArrayList<Integer> > adj
= new HashMap<>();
HashMap<Integer, Integer> indegree
= new HashMap<>();
// Initializing all keys of map
// with values of sequences in arr
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
int node = arr.get(i).get(j);
ArrayList<Integer> temp
= new ArrayList<Integer>();
adj.put(node, temp);
indegree.put(node, 0);
}
}
// For every sequence in arr
// calculate indegree and edges.
for (ArrayList<Integer> seq : arr) {
for (int i = 1; i < M; i++) {
adj.get(seq.get(i - 1)).add(seq.get(i));
int temp = indegree.get(seq.get(i));
indegree.put(seq.get(i), temp + 1);
}
}
// ArrayList to store
// topologically sorted order.
ArrayList<Integer> res = new ArrayList<Integer>();
ArrayDeque<Integer> q = new ArrayDeque<>();
// Push vertices with 0 indegree in queue
for (int itr : indegree.keySet()) {
if (indegree.get(itr) == 0) {
q.addLast(itr);
}
}
while (q.size() > 0) {
int size = q.size();
// If size of q > 1, this means
// more than one choices,
// so no unique common supersequence
// can be formed.
if (size != 1)
return false;
int node = q.getFirst();
// Add node to topological sort order
res.add(node);
q.removeLast();
// Decrement indegree of all
// the vertices connected to node
for (int i = 0; i < adj.get(node).size(); i++) {
int connected_node = adj.get(node).get(i);
// Push vertices with 0 indegree
// to queue
int temp = indegree.get(connected_node) - 1;
indegree.put(connected_node, temp);
if ((temp == 0)) {
q.addLast(connected_node);
}
}
}
// If indegree of any vertices is not 0,
// return false.
for (int itr : indegree.keySet()) {
if (indegree.get(itr) != 0)
return false;
}
return true;
}
// Driver Code
public static void main(String[] args)
{
ArrayList<ArrayList<Integer> > arr
= new ArrayList<ArrayList<Integer> >();
arr.add(
new ArrayList<Integer>(Arrays.asList(1, 2)));
arr.add(
new ArrayList<Integer>(Arrays.asList(1, 3)));
int N = arr.size(), M = arr.get(0).size();
if (shortestSuperSeq(arr, N, M))
System.out.println("True");
else
System.out.println("False");
}
}
// This code is contributed by Palak Gupta
Python3
# Python code for the above approach
# Function to check unique
# shortest common supersequence
def shortestSuperSeq(arr, N, M):
# Initializing map to store
# edges and indegree of vertices
adj = {}
indegree = {}
# Initializing all keys of map
# with values of sequences in arr
for i in range(N):
for j in range(M):
node = arr[i][j];
adj[node] = []
indegree[node] = 0
# For every sequence in arr
# calculate indegree and edges.
for seq in arr:
for i in range(1, M):
adj[seq[i - 1]].append(seq[i]);
indegree[seq[i]] += 1
# Vector to store
# topologically sorted order.
res = [];
q = [];
# Push vertices with 0 indegree in queue
for k in indegree.keys():
if (indegree[k] == 0):
q.append(k);
while (len(q) != 0):
size = len(q)
# If size of q > 1, this means
# more than one choices,
# so no unique common supersequence
# can be formed.
if (size != 1):
return False;
node = q.pop(0);
# Add node to topological sort order
res.append(node);
# Decrement indegree of all
# the vertices connected to node
for i in range(len(adj[node])):
connected_node = adj[node][i];
# Push vertices with 0 indegree
# to queue
indegree[connected_node] -= 1
if (indegree[connected_node] == 0):
q.append(connected_node);
# If indegree of any vertices is not 0,
# return false.
for itr in indegree.keys():
if (itr != 0):
return False;
return True;
# Driver Code
arr = [[1, 2], [1, 3]];
N = len(arr)
M = len(arr[0])
if (shortestSuperSeq(arr, N, M)):
print("True");
else:
print("False")
# This code is contributed by Saurabh Jaiswal
C#
// C# program to implement above approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
// Function to check unique
// shortest common supersequence
static bool shortestSuperSeq(List<List<int>> arr, int N, int M)
{
// Initializing map to store
// edges and indegree of vertices
Dictionary<int, List<int>> adj = new Dictionary<int, List<int>>();
Dictionary<int, int> indegree = new Dictionary<int, int>();
// Initializing all keys of map
// with values of sequences in arr
for (int i = 0 ; i < N ; i++) {
for (int j = 0 ; j < M ; j++) {
int node = arr[i][j];
if(!adj.ContainsKey(node)){
adj.Add(node, new List<int>());
indegree.Add(node, 0);
}
}
}
// For every sequence in arr
// calculate indegree and edges.
foreach (List<int> seq in arr) {
for (int i = 1 ; i < M ; i++) {
if(!adj.ContainsKey(seq[i-1])){
adj.Add(seq[i-1], new List<int>());
}
adj[seq[i-1]].Add(seq[i]);
if(!indegree.ContainsKey(seq[i])){
indegree.Add(seq[i], 0);
}
int temp = indegree[seq[i]];
indegree[seq[i]] = temp + 1;
}
}
// ArrayList to store
// topologically sorted order.
List<int> res = new List<int>();
List<int> q = new List<int>();
// Pointers to first and last element of deque
int l = 0, r = -1;
// Push vertices with 0 indegree in queue
foreach (KeyValuePair<int, int> itr in indegree) {
if (indegree[itr.Key] == 0) {
q.Add(itr.Key);
r++;
}
}
while (l <= r) {
int size = r - l + 1;
// If size of q > 1, this means
// more than one choices,
// so no unique common supersequence
// can be formed.
if (size != 1)
return false;
int node = q[l];
// Add node to topological sort order
res.Add(node);
r--;
// Decrement indegree of all
// the vertices connected to node
for (int i = 0 ; i < adj[node].Count ; i++) {
int connected_node = adj[node][i];
// Push vertices with 0 indegree
// to queue
int temp = indegree[connected_node] - 1;
indegree[connected_node] = temp;
if (temp == 0) {
if(q.Count - 1 == r){
q.Add(connected_node);
}else{
q[r + 1] = connected_node;
}
r++;
}
}
}
// If indegree of any vertices is not 0,
// return false.
foreach (KeyValuePair<int, int> itr in indegree) {
if (itr.Value != 0)
return false;
}
return true;
}
public static void Main(string[] args){
List<List<int>> arr = new List<List<int>>();
arr.Add(new List<int>{1, 2});
arr.Add(new List<int>{1, 3});
int N = arr.Count;
int M = arr[0].Count;
if (shortestSuperSeq(arr, N, M))
Console.WriteLine("True");
else
Console.WriteLine("False");
}
}
// This code is contributed by entertain2022.
Javascript
<script>
// JavaScript code for the above approach
// Function to check unique
// shortest common supersequence
function shortestSuperSeq(arr,
N, M)
{
// Initializing map to store
// edges and indegree of vertices
let adj = new Map();
let indegree = new Map();
// Initializing all keys of map
// with values of sequences in arr
for (let i = 0; i < N; i++) {
for (let j = 0; j < M; j++) {
let node = arr[i][j];
adj.set(node, [])
indegree.set(node, 0);
}
}
// For every sequence in arr
// calculate indegree and edges.
for (let seq of arr) {
for (let i = 1; i < M; i++) {
adj.get(seq[i - 1]).push(seq[i]);
indegree.set(seq[i], indegree.get(seq[i]) + 1);
}
}
// Vector to store
// topologically sorted order.
let res = [];
let q = [];
// Push vertices with 0 indegree in queue
for (let [key, val] of indegree) {
if (val == 0) {
q.push(key);
}
}
while (q.length != 0) {
let size = q.length;
// If size of q > 1, this means
// more than one choices,
// so no unique common supersequence
// can be formed.
if (size != 1)
return false;
let node = q.shift();
// Add node to topological sort order
res.push(node);
// Decrement indegree of all
// the vertices connected to node
for (let i = 0; i < adj.get(node).length;
i++) {
let connected_node = adj.get(node)[i];
// Push vertices with 0 indegree
// to queue
indegree.set(connected_node, indegree.get(connected_node) - 1);
if ((indegree.get(connected_node))
== 0) {
q.push(connected_node);
}
}
}
// If indegree of any vertices is not 0,
// return false.
for (let itr of indegree.keys()) {
if (itr != 0)
return false;
}
return true;
}
// Driver Code
let arr = [[1, 2],
[1, 3]];
let N = arr.length, M = arr[0].length;
if (shortestSuperSeq(arr, N, M))
document.write("True");
else
document.write("False")
// This code is contributed by Potta Lokesh
</script>
Producción
False
Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)