Dado un número entero N y dos arrays A[][] , que representan el conjunto de idiomas que una persona conoce, y B[][] , que consta de M pares de amistades, la tarea es encontrar el número mínimo de personas a las que se les enseñará un un solo idioma para que cada par de amigos puedan comunicarse entre sí.
Ejemplos:
Entrada: N = 2, A[][] = {{1}, {2}, {1, 2}}, B[][] = {{1, 2}, {1, 3}, {2, 3}}
Salida: 1
Explicación:
Una forma posible es enseñarle a la 1ª persona el idioma 2.
Otra forma posible es enseñarle a la 2ª persona el idioma 1.
Por lo tanto, el número mínimo de idiomas necesarios para enseñar es 1.Entrada: N = 4, A[][] = {{2}, {1, 4}, {1, 2}, {3, 4}}, B[][] = {{1, 4}, { 1, 2}, {3, 4}, {2, 3}}
Salida: 2
Explicación:
Una de las formas posibles es enseñarle a la 1ª persona el idioma 3 o 4 y a la 3ª persona el idioma 3 o 4.
Por lo tanto, el número mínimo de idiomas requeridos para ser enseñados es de 2.
Enfoque: el problema dado se puede resolver utilizando una estructura de datos de conjunto y mapa para resolver el problema dado.
Siga los pasos a continuación para resolver el problema:
- Defina una función, digamos Check(A[], B[]) , para verificar si algún elemento común está presente en las dos arrays ordenadas o no :
- Defina dos variables, digamos P1 y P2 para almacenar los punteros.
- Iterar mientras P1 < M y P2 < N . Si A[P1] es igual a B[P2] , devuelve verdadero. De lo contrario, si A[P1] < B[P2] , incremente P1 en uno. De lo contrario, si A[P1] > B[P2] , incremente P2 en 1 .
- Si ninguno de los casos anteriores satisface, devuelva falso.
- Inicialice un set<int> , digamos S , y un map<int, int> , digamos mp , para almacenar todas las personas que no pueden comunicarse con sus amigos y contar las personas que hablan un idioma en particular.
- Inicialice una variable, digamos resultado , para almacenar el recuento de personas a las que se les enseñará.
- Recorra la array B[][] e inserte el par de personas si no hay un lenguaje común entre ellas llamando a la función Verificar(B[i][0], B[i][1]).
- Recorra el conjunto S de los idiomas que una persona conoce e incremente el conteo de ese idioma en el Mapa mp .
- Recorra el map<int, int> mp y actualice el resultado como resultado = min(S.size() – it.second, result).
- Finalmente, después de completar los pasos anteriores, imprima el resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of
// the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if there
// exists any common language
bool check(vector<int>& a, vector<int>& b)
{
// Stores the size of array a[]
int M = a.size();
// Stores the size of array b[]
int N = b.size();
// Pointers
int p1 = 0, p2 = 0;
// Iterate while p1 < M and p2 < N
while (p1 < M && p2 < N) {
if (a[p1] < b[p2])
p1++;
else if (a[p1] > b[p2])
p2++;
else
return true;
}
return false;
}
// Function to count the minimum number
// of people required to be teached
int minimumTeachings(
int N, vector<vector<int> >& languages,
vector<vector<int> > friendships)
{
// Stores the size of array A[][]
int m = languages.size();
// Stores the size of array B[][]
int t = friendships.size();
// Stores all the persons with no
// common languages with their friends
unordered_set<int> total;
// Stores count of languages
unordered_map<int, int> overall;
// Sort all the languages of
// a person in ascending order
for (int i = 0; i < m; i++)
sort(languages[i].begin(),
languages[i].end());
// Traverse the array B[][]
for (int i = 0; i < t; i++) {
// Check if there is no common
// language between two friends
if (!check(languages[friendships[i][0] - 1],
languages[friendships[i][1] - 1])) {
// Insert the persons in the Set
total.insert(friendships[i][0]);
total.insert(friendships[i][1]);
}
}
// Stores the size of the Set
int s = total.size();
// Stores the count of
// minimum persons to teach
int result = s;
// Traverse the set total
for (auto p : total) {
// Traverse A[p - 1]
for (int i = 0;
i < languages[p - 1].size(); i++)
// Increment count of languages by one
overall[languages[p - 1][i]]++;
}
// Traverse the map
for (auto c : overall)
// Update result
result = min(result, s - c.second);
// Return the result
return result;
}
// Driver Code
int main()
{
int N = 3;
vector<vector<int> > A
= { { 1 }, { 1, 3 }, { 1, 2 }, { 3 } };
vector<vector<int> > B
= { { 1, 4 }, { 1, 2 }, { 3, 4 }, { 2, 3 } };
cout << minimumTeachings(N, A, B) << endl;
return 0;
}
Java
// Java implementation of
// the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to check if there
// exists any common language
static boolean check(int a[], int b[])
{
// Stores the size of array a[]
int M = a.length;
// Stores the size of array b[]
int N = b.length;
// Pointers
int p1 = 0, p2 = 0;
// Iterate while p1 < M and p2 < N
while (p1 < M && p2 < N)
{
if (a[p1] < b[p2])
p1++;
else if (a[p1] > b[p2])
p2++;
else
return true;
}
return false;
}
// Function to count the minimum number
// of people required to be teached
static int minimumTeachings(int N, int languages[][],
int friendships[][])
{
// Stores the size of array A[][]
int m = languages.length;
// Stores the size of array B[][]
int t = friendships.length;
// Stores all the persons with no
// common languages with their friends
HashSet<Integer> total = new HashSet<>();
// Stores count of languages
HashMap<Integer, Integer> overall = new HashMap<>();
// Sort all the languages of
// a person in ascending order
for(int i = 0; i < m; i++)
Arrays.sort(languages[i]);
// Traverse the array B[][]
for(int i = 0; i < t; i++)
{
// Check if there is no common
// language between two friends
if (!check(languages[friendships[i][0] - 1],
languages[friendships[i][1] - 1]))
{
// Insert the persons in the Set
total.add(friendships[i][0]);
total.add(friendships[i][1]);
}
}
// Stores the size of the Set
int s = total.size();
// Stores the count of
// minimum persons to teach
int result = s;
// Traverse the set total
for(int p : total)
{
// Traverse A[p - 1]
for(int i = 0; i < languages[p - 1].length; i++)
// Increment count of languages by one
overall.put(languages[p - 1][i],
overall.getOrDefault(
languages[p - 1][i], 0) + 1);
}
// Traverse the map
for(int k : overall.keySet())
// Update result
result = Math.min(result, s - overall.get(k));
// Return the result
return result;
}
// Driver Code
public static void main(String[] args)
{
int N = 3;
int A[][] = { { 1 }, { 1, 3 },
{ 1, 2 }, { 3 } };
int B[][] = { { 1, 4 }, { 1, 2 },
{ 3, 4 }, { 2, 3 } };
System.out.println(minimumTeachings(N, A, B));
}
}
// This code is contributed by Kingash
Python3
# Python3 implementation of
# the above approach
# Function to check if there
# exists any common language
def check(a, b):
# Stores the size of array a[]
M = len(a)
# Stores the size of array b[]
N = len(b)
# Pointers
p1 = 0
p2 = 0
# Iterate while p1 < M and p2 < N
while(p1 < M and p2 < N):
if (a[p1] < b[p2]):
p1 += 1
elif(a[p1] > b[p2]):
p2 += 1
else:
return True
return False
# Function to count the minimum number
# of people required to be teached
def minimumTeachings(N, languages, friendships):
# Stores the size of array A[][]
m = len(languages)
# Stores the size of array B[][]
t = len(friendships)
# Stores all the persons with no
# common languages with their friends
total = set()
# Stores count of languages
overall = {}
# Sort all the languages of
# a person in ascending order
for i in range(m):
languages[i].sort(reverse=False)
# Traverse the array B[][]
for i in range(t):
# Check if there is no common
# language between two friends
if(check(languages[friendships[i][0] - 1], languages[friendships[i][1] - 1])==False):
# Insert the persons in the Set
total.add(friendships[i][0])
total.add(friendships[i][1])
# Stores the size of the Set
s = len(total)
# Stores the count of
# minimum persons to teach
result = s
# Traverse the set total
for p in total:
# Traverse A[p - 1]
for i in range(len(languages[p - 1])):
# Increment count of languages by one
if languages[p - 1][i] in overall:
overall[languages[p - 1][i]] += 1
else:
overall[languages[p - 1][i]] = 1
# Traverse the map
for keys,value in overall.items():
# Update result
result = min(result, s - value)
# Return the result
return result
# Driver Code
if __name__ == '__main__':
N = 3
A = [[1],[1, 3],[1, 2],[3]]
B = [[1, 4],[1, 2],[3, 4],[2, 3]]
print(minimumTeachings(N, A, B))
# This code is contributed by ipg2016107.
C#
// C# implementation of
// the above approach
using System;
using System.Collections.Generic;
class GFG {
// Function to check if there
// exists any common language
static bool check(int[] a, int[] b)
{
// Stores the size of array a[]
int M = a.Length;
// Stores the size of array b[]
int N = b.Length;
// Pointers
int p1 = 0, p2 = 0;
// Iterate while p1 < M and p2 < N
while (p1 < M && p2 < N)
{
if (a[p1] < b[p2])
p1++;
else if (a[p1] > b[p2])
p2++;
else
return true;
}
return false;
}
// Function to count the minimum number
// of people required to be teached
static int minimumTeachings(int N, int[,] languages,
int[,] friendships)
{
// Stores the size of array A[][]
int m = languages.Length;
int[] arr1 = {1,2,3};
// Stores the size of array B[][]
int t = friendships.Length;
int[] arr2 = {1,2,3};
// Stores all the persons with no
// common languages with their friends
HashSet<int> total = new HashSet<int>();
// Stores count of languages
Dictionary<int, int> overall = new Dictionary<int, int>();
// Sort all the languages of
// a person in ascending order
for(int i = 0; i < m; i++)
Array.Sort(arr1);
// Traverse the array B[][]
for(int i = 0; i < t; i++)
{
// Check if there is no common
// language between two friends
if (!check(arr1,arr2))
{
// Insert the persons in the Set
total.Add(friendships[i,0]);
total.Add(friendships[i,1]);
}
}
// Stores the size of the Set
int s = total.Count;
// Stores the count of
// minimum persons to teach
int result = s+1;
// Traverse the set total
foreach(int p in total)
{
// Traverse A[p - 1]
for(int i = 0; i < languages.GetLength(1); i++)
// Increment count of languages by one
overall[languages[p - 1,i]]+=1;
}
// Traverse the map
foreach(KeyValuePair<int, int> k in overall)
{
result = Math.Min(result, s - k.Value);
}
// Return the result
return result;
}
static void Main() {
int N = 3;
int[,] A = { { 1, 0 }, { 1, 3 },
{ 1, 2 }, { 3, 0 } };
int[,] B = { { 1, 4 }, { 1, 2 },
{ 3, 4 }, { 2, 3 } };
Console.Write(minimumTeachings(N, A, B));
}
}
Javascript
<script>
// Javascript implementation of
// the above approach
// Function to check if there
// exists any common language
function check(a, b)
{
// Stores the size of array a[]
let M = a.length;
// Stores the size of array b[]
let N = b.length;
// Pointers
let p1 = 0, p2 = 0;
// Iterate while p1 < M and p2 < N
while (p1 < M && p2 < N)
{
if (a[p1] < b[p2])
p1++;
else if (a[p1] > b[p2])
p2++;
else
return true;
}
return false;
}
// Function to count the minimum number
// of people required to be teached
function minimumTeachings(N, languages, friendships)
{
// Stores the size of array A[][]
let m = languages.length;
// Stores the size of array B[][]
let t = friendships.length;
// Stores all the persons with no
// common languages with their friends
let total = new Set();
// Stores count of languages
let overall = new Map();
// Sort all the languages of
// a person in ascending order
for(let i = 0; i < m; i++)
languages[i].sort((a, b) => a - b);
// Traverse the array B[][]
for(let i = 0; i < t; i++)
{
// Check if there is no common
// language between two friends
if (!check(languages[friendships[i][0] - 1],
languages[friendships[i][1] - 1]))
{
// Insert the persons in the Set
total.add(friendships[i][0]);
total.add(friendships[i][1]);
}
}
// Stores the size of the Set
let s = total.size;
// Stores the count of
// minimum persons to teach
let result = s;
// Traverse the set total
for(let p of total)
{
// Traverse A[p - 1]
for(let i = 0; i < languages[p - 1].length; i++)
{
// Increment count of languages by one
if (overall.has(languages[p - 1][i]))
{
overall.set(languages[p - 1][i],
overall.get(languages[p - 1][i]) + 1)
}
else
{
overall.set(languages[p - 1][i], 1)
}
}
}
// Traverse the map
for(let c of overall)
// Update result
result = Math.min(result, s - c[1]);
// Return the result
return result;
}
// Driver Code
let N = 3;
let A = [ [ 1 ], [ 1, 3 ],
[ 1, 2 ], [ 3 ] ];
let B = [ [ 1, 4 ], [ 1, 2 ],
[ 3, 4 ], [ 2, 3 ] ];
document.write(minimumTeachings(N, A, B) + "<br>");
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)