Dado un grupo de N personas, cada una con un valor de ID único de 0 a (N – 1) y una array arr[] de M elementos de la forma {U, V, tiempo} que representa que la persona U se familiarizará con la persona V en el momento dado . Digamos que la persona U conoce a la persona V si U es amigo de V , o U es amigo de alguien que conoce a V. La tarea es encontrar el momento más temprano en el que cada persona se conoció entre sí.
Ejemplos:
Entrada: N = 4, arr[] = {{0, 1, 2}, {1, 2, 3}, {2, 3, 4}}
Salida: 4
Explicación: Inicialmente, el número de personas es 4, es decir , {0}, {1}, {2}, {3}.
- En el momento = 2, {0} y {1} se hicieron amigos. Por lo tanto, el grupo de personas conocidas se convierte en {0, 1}, {2}, {3}.
- En el tiempo = 3, {1} y {2} se hicieron amigos. Por lo tanto, el grupo de personas conocidas se convierte en {0, 1, 2}, {3}.
- En el momento = 4, {2} y {3} se hicieron amigos. Por lo tanto, el grupo de personas conocidas se convierte en {0, 1, 2, 3}.
Por lo tanto, en el tiempo = 4, todas las personas se conocieron.
Entrada: N = 6, arr[] = {{0, 1, 4}, {3, 4, 5}, {2, 3, 14}, {1, 5, 24}, {2, 4, 12} , {0, 3, 42}, {1, 2, 41}, {4, 5, 11}}
Salida: 24
Enfoque: el problema dado se puede resolver utilizando la estructura de datos de unión de conjuntos disjuntos . La idea es realizar las operaciones de unión entre personas en orden de valor creciente del tiempo. La respuesta requerida será el momento en que todas las personas pertenezcan al mismo conjunto. Siga los pasos a continuación para resolver el problema dado:
- Implemente la estructura de datos de unión de conjuntos disjuntos con las funciones union y findSet de acuerdo con el algoritmo discutido aquí .
- Inicialice una variable time , que almacena el valor de la marca de tiempo actual de la DSU.
- Ordene la array dada arr[] en orden creciente de tiempo.
- Recorra la array dada arr[] usando la variable i y realice la operación de unión entre (U i , V i ) y actualice la marca de tiempo actual a la hora i si U i y V i pertenecen a conjuntos diferentes.
- Si el número total de conjuntos después de recorrer completamente la array arr[] es 1 , devuelva el valor de la variable time , de lo contrario, devuelva -1 .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include "bits/stdc++.h"
using namespace std;
// Implementation of DSU
class UnionFind {
vector<int> parent, rank;
// Stores the current timestamp
int time;
// Stores the count of current sets
int count;
public:
// Constructor to create and
// initialize sets of N items
UnionFind(int N)
: parent(N), rank(N), count(N)
{
time = 0;
// Creates N single item sets
for (int i = 0; i < N; i++) {
parent[i] = i;
rank[i] = 1;
}
}
// Function to find the set of
// given item node
int find(int node)
{
if (node == parent[node])
return node;
return parent[node]
= find(parent[node]);
}
// Function to perform the union of
// two sets represented by u and v,
// and update the value of time
void performUnion(int u, int v,
int updatedTime)
{
if (count == 1)
return;
// Find current sets of u and v
int rootX = find(u);
int rootY = find(v);
if (rootX != rootY) {
// Put smaller ranked item under
// bigger ranked item if ranks
// are different
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
}
else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
}
else {
parent[rootX] = rootY;
rank[rootY] += 1;
}
// Update the value of the
// current timestamp
time = updatedTime;
// Update the value of
// set count
count--;
}
}
// Function to return current
// set count
int getCount() { return count; }
// Function to return current
// time stamp
int getTime() { return time; }
};
// Comparator function to sort the array
// in increasing order of 3rd element
bool cmp(vector<int>& A, vector<int>& B)
{
return A[2] <= B[2];
}
// Function to find the earliest time when
// everyone became friends to each other
int earliestTime(vector<vector<int> >& arr,
int N)
{
// Sort array arr[] in increasing order
sort(arr.begin(), arr.end(), cmp);
// Initialize a DSU with N elements
UnionFind unionFind(N);
// Iterate over array arr[] perform
// union operation for each element
for (auto& it : arr) {
// Perform union operation on
// it[0] and it[1] and update
// timestamp to it[2]
unionFind.performUnion(
it[0], it[1], it[2]);
}
// Return Answer
if (unionFind.getCount() == 1) {
return unionFind.getTime();
}
else {
return -1;
}
}
// Driver Code
int main()
{
int N = 6;
vector<vector<int> > arr
= { { 0, 1, 4 }, { 3, 4, 5 },
{ 2, 3, 14 }, { 1, 5, 24 },
{ 2, 4, 12 }, { 0, 3, 42 },
{ 1, 2, 41 }, { 4, 5, 11 } };
cout << earliestTime(arr, N);
return 0;
}
24
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA