Considere una red social especial donde las personas se llaman conectadas si una persona está conectada a otra con cualquier cantidad de conexiones intermedias. Por ejemplo, si una persona x está conectada con y y y está conectada con z, entonces x también se considera conectada con z. Recibimos un conjunto de requests de amistad como entrada. También tenemos un conjunto de consultas donde cada consulta tiene un par de entradas i y j. Para cada consulta, necesitamos saber si i y j están conectados o no.
Ejemplos:
Entrada: Conexiones:
conectar (0, 1), conectar (1, 2), conectar (0, 3), conectar (5, 6), conectar (0, 7)
están conectados (2, 7)
están conectados (2, 6)
areConnected(1, 7)
Salida:
Sí
No
Sí
Explicación: tenga en cuenta que 0 está conectado a 2 y 0 también está conectado a 7. Por lo tanto, 2 y 7 se consideran conectados.Entrada: Conexiones:
conectar (0, 2), conectar (4, 2), conectar (1, 3)
están conectados (0, 4)
están conectados (0, 1)
Salida:
Sí
No
La idea es utilizar una estructura de datos de conjuntos disjuntos . Con esta estructura de datos, podemos resolver todas las consultas en O(1) tiempo amortizado.
// A Java program to implement Special Social Network // using Disjoint Set Data Structure. import java.io.*; import java.util.*; class DisjointUnionSets { int[] rank, parent; int n; // Constructor public DisjointUnionSets(int n) { rank = new int[n]; parent = new int[n]; this.n = n; makeSet(); } // Creates n sets with single item in each void makeSet() { for (int i = 0; i < n; i++) { // Initially, all elements are in // their own set. parent[i] = i; } } // Returns representative of x's set int find(int x) { // Finds the representative of the set // that x is an element of if (parent[x] != x) { // if x is not the parent of itself // Then x is not the representative of // his set, parent[x] = find(parent[x]); // so we recursively call Find on its parent // and move i's node directly under the // representative of this set } return parent[x]; } // Unites the set that includes x and the set // that includes x void connect(int x, int y) { // Find representatives of two sets int xRoot = find(x), yRoot = find(y); // Elements are in the same set, no need // to unite anything. if (xRoot == yRoot) return; // If x's rank is less than y's rank if (rank[xRoot] < rank[yRoot]) // Then move x under y so that depth // of tree remains less parent[xRoot] = yRoot; // Else if y's rank is less than x's rank else if (rank[yRoot] < rank[xRoot]) // Then move y under x so that depth of // tree remains less parent[yRoot] = xRoot; else // if ranks are the same { // Then move y under x (doesn't matter // which one goes where) parent[yRoot] = xRoot; // And increment the the result tree's // rank by 1 rank[xRoot] = rank[xRoot] + 1; } } boolean areConnected(int i, int j) { return find(i) == find(j); } } // Driver code public class Main { public static void main(String[] args) { // Let there be 5 persons with ids as // 0, 1, 2, 3 and 4 int n = 5; DisjointUnionSets dus = new DisjointUnionSets(n); // 0 is a friend of 2 dus.connect(0, 2); // 4 is a friend of 2 dus.connect(4, 2); // 3 is a friend of 1 dus.connect(3, 1); // Check if 4 is a friend of 0 if (dus.areConnected(0, 4)) System.out.println("Yes"); else System.out.println("No"); // Check if 1 is a friend of 0 if (dus.areConnected(0, 1)) System.out.println("Yes"); else System.out.println("No"); } }
Yes No