Conectividad Dinámica | Conjunto 1 (incremental)

La conectividad dinámica es una estructura de datos que mantiene dinámicamente la información sobre los componentes conectados del gráfico. En palabras simples, supongamos que hay un gráfico G(V, E) en el que no. de vértices V es constante pero no. de aristas E es variable. Hay tres formas en las que podemos cambiar el número de aristas

1. Conectividad incremental: los bordes solo se agregan al gráfico.
2. Conectividad decremental: los bordes solo se eliminan del gráfico.
3. Conectividad totalmente dinámica: los bordes se pueden eliminar y agregar al gráfico.

En este artículo solo se analiza la conectividad incremental . Hay principalmente dos operaciones que necesitan ser manejadas. 

1. Se agrega un borde al gráfico.
2. Información sobre dos Nodes xey si están en los mismos componentes conectados o no.

Ejemplo: 

Input : V = 7
        Number of operations = 11
        1 0 1
        2 0 1
        2 1 2
        1 0 2
        2 0 2
        2 2 3
        2 3 4
        1 0 5
        2 4 5
        2 5 6
        1 2 6
Note: 7 represents number of nodes, 
      11 represents number of queries. 
      There are two types of queries 
      Type 1: 1 x y in  this if the node 
               x and y are connected print 
               Yes else No
      Type 2: 2 x y in this add an edge 
               between node x and y
Output: No
         Yes
         No
         Yes
Explanation :
Initially there are no edges so node 0 and 1
will be disconnected so answer will be No
Node 0 and 2 will be connected through node 
1 so answer will be Yes similarly for other
queries we can find whether two nodes are 
connected or not

Para resolver los problemas de conectividad incremental se utiliza la estructura de datos disjuntos . Aquí cada componente conectado representa un conjunto y si los dos Nodes pertenecen al mismo conjunto significa que están conectados. 

La implementación se da a continuación aquí estamos usando unión por rango y compresión de ruta 

// C++ implementation of incremental connectivity
#include<bits/stdc++.h>
using namespace std;
 
// Finding the root of node i
int root(int arr[], int i)
{
    while (arr[i] != i)
    {
       arr[i] = arr[arr[i]];
       i = arr[i];
    }
    return i;
}
 
// union of two nodes a and b
void weighted_union(int arr[], int rank[],
                            int a, int b)
{
    int root_a = root (arr, a);
    int root_b = root (arr, b);
 
    // union based on rank
    if (rank[root_a] < rank[root_b])
    {
       arr[root_a] = arr[root_b];
       rank[root_b] += rank[root_a];
    }
    else
    {
        arr[root_b] = arr[root_a];
        rank[root_a] += rank[root_b];
    }
}
 
// Returns true if two nodes have same root
bool areSame(int arr[], int a, int b)
{
    return (root(arr, a) == root(arr, b));
}
 
// Performing an operation according to query type
void query(int type, int x, int y, int arr[], int rank[])
{
    // type 1 query means checking if node x and y
    // are connected or not
    if (type == 1)
    {
        // If roots of x and y is same then yes
        // is the answer
        if (areSame(arr, x, y) == true)
            cout << "Yes" << endl;
        else
           cout << "No" << endl;
    }
 
    // type 2 query refers union of x and y
    else if (type == 2)
    {
        // If x and y have different roots then
        // union them
        if (areSame(arr, x, y) == false)
            weighted_union(arr, rank, x, y);
    }
}
 
// Driver function
int main()
{
    // No.of nodes
    int n = 7;
 
    // The following two arrays are used to
    // implement disjoint set data structure.
    // arr[] holds the parent nodes while rank
    // array holds the rank of subset
    int arr[n], rank[n];
 
    // initializing both array and rank
    for (int i=0; i<n; i++)
    {
        arr[i] = i;
        rank[i] = 1;
    }
 
    // number of queries
    int q = 11;
    query(1, 0, 1, arr, rank);
    query(2, 0, 1, arr, rank);
    query(2, 1, 2, arr, rank);
    query(1, 0, 2, arr, rank);
    query(2, 0, 2, arr, rank);
    query(2, 2, 3, arr, rank);
    query(2, 3, 4, arr, rank);
    query(1, 0, 5, arr, rank);
    query(2, 4, 5, arr, rank);
    query(2, 5, 6, arr, rank);
    query(1, 2, 6, arr, rank);
    return 0;
}

// Java implementation of
// incremental connectivity
import java.util.*;
 
class GFG
{
 
// Finding the root of node i
static int root(int arr[], int i)
{
    while (arr[i] != i)
    {
        arr[i] = arr[arr[i]];
        i = arr[i];
    }
    return i;
}
 
// union of two nodes a and b
static void weighted_union(int arr[], int rank[],
                           int a, int b)
{
    int root_a = root (arr, a);
    int root_b = root (arr, b);
 
    // union based on rank
    if (rank[root_a] < rank[root_b])
    {
        arr[root_a] = arr[root_b];
        rank[root_b] += rank[root_a];
    }
    else
    {
        arr[root_b] = arr[root_a];
        rank[root_a] += rank[root_b];
    }
}
 
// Returns true if two nodes have same root
static boolean areSame(int arr[],
                       int a, int b)
{
    return (root(arr, a) == root(arr, b));
}
 
// Performing an operation
// according to query type
static void query(int type, int x, int y,
                  int arr[], int rank[])
{
    // type 1 query means checking if
    // node x and y are connected or not
    if (type == 1)
    {
        // If roots of x and y is same then yes
        // is the answer
        if (areSame(arr, x, y) == true)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
 
    // type 2 query refers union of x and y
    else if (type == 2)
    {
        // If x and y have different roots then
        // union them
        if (areSame(arr, x, y) == false)
            weighted_union(arr, rank, x, y);
    }
}
 
// Driver Code
public static void main(String[] args)
{
    // No.of nodes
    int n = 7;
 
    // The following two arrays are used to
    // implement disjoint set data structure.
    // arr[] holds the parent nodes while rank
    // array holds the rank of subset
    int []arr = new int[n];
    int []rank = new int[n];
 
    // initializing both array and rank
    for (int i = 0; i < n; i++)
    {
        arr[i] = i;
        rank[i] = 1;
    }
 
    // number of queries
    int q = 11;
    query(1, 0, 1, arr, rank);
    query(2, 0, 1, arr, rank);
    query(2, 1, 2, arr, rank);
    query(1, 0, 2, arr, rank);
    query(2, 0, 2, arr, rank);
    query(2, 2, 3, arr, rank);
    query(2, 3, 4, arr, rank);
    query(1, 0, 5, arr, rank);
    query(2, 4, 5, arr, rank);
    query(2, 5, 6, arr, rank);
    query(1, 2, 6, arr, rank);
}
}
 
// This code is contributed by Rajput-Ji

# Python3 implementation of
# incremental connectivity
 
# Finding the root of node i
def root(arr, i):
    while (arr[i] != i):
        arr[i] = arr[arr[i]]
        i = arr[i]
    return i
 
# union of two nodes a and b
def weighted_union(arr, rank, a, b):
    root_a = root (arr, a)
    root_b = root (arr, b)
 
    # union based on rank
    if (rank[root_a] < rank[root_b]):
        arr[root_a] = arr[root_b]
        rank[root_b] += rank[root_a]
    else:
        arr[root_b] = arr[root_a]
        rank[root_a] += rank[root_b]
 
# Returns true if two nodes have
# same root
def areSame(arr, a, b):
    return (root(arr, a) == root(arr, b))
 
# Performing an operation according
# to query type
def query(type, x, y, arr, rank):
     
    # type 1 query means checking if
    # node x and y are connected or not
    if (type == 1):
         
        # If roots of x and y is same
        # then yes is the answer
        if (areSame(arr, x, y) == True):
            print("Yes")
        else:
            print("No")
 
    # type 2 query refers union of
    # x and y
    elif (type == 2):
         
        # If x and y have different
        # roots then union them
        if (areSame(arr, x, y) == False):
            weighted_union(arr, rank, x, y)
 
# Driver Code
if __name__ == '__main__':
 
    # No.of nodes
    n = 7
 
    # The following two arrays are used to
    # implement disjoint set data structure.
    # arr[] holds the parent nodes while rank
    # array holds the rank of subset
    arr = [None] * n
    rank = [None] * n
 
    # initializing both array
    # and rank
    for i in range(n):
        arr[i] = i
        rank[i] = 1
 
    # number of queries
    q = 11
    query(1, 0, 1, arr, rank)
    query(2, 0, 1, arr, rank)
    query(2, 1, 2, arr, rank)
    query(1, 0, 2, arr, rank)
    query(2, 0, 2, arr, rank)
    query(2, 2, 3, arr, rank)
    query(2, 3, 4, arr, rank)
    query(1, 0, 5, arr, rank)
    query(2, 4, 5, arr, rank)
    query(2, 5, 6, arr, rank)
    query(1, 2, 6, arr, rank)
 
# This code is contributed by PranchalK

// C# implementation of
// incremental connectivity
using System;
     
class GFG
{
 
// Finding the root of node i
static int root(int []arr, int i)
{
    while (arr[i] != i)
    {
        arr[i] = arr[arr[i]];
        i = arr[i];
    }
    return i;
}
 
// union of two nodes a and b
static void weighted_union(int []arr, int []rank,
                           int a, int b)
{
    int root_a = root (arr, a);
    int root_b = root (arr, b);
 
    // union based on rank
    if (rank[root_a] < rank[root_b])
    {
        arr[root_a] = arr[root_b];
        rank[root_b] += rank[root_a];
    }
    else
    {
        arr[root_b] = arr[root_a];
        rank[root_a] += rank[root_b];
    }
}
 
// Returns true if two nodes have same root
static Boolean areSame(int []arr,
                       int a, int b)
{
    return (root(arr, a) == root(arr, b));
}
 
// Performing an operation
// according to query type
static void query(int type, int x, int y,
                  int []arr, int []rank)
{
    // type 1 query means checking if
    // node x and y are connected or not
    if (type == 1)
    {
        // If roots of x and y is same then yes
        // is the answer
        if (areSame(arr, x, y) == true)
            Console.WriteLine("Yes");
        else
            Console.WriteLine("No");
    }
 
    // type 2 query refers union of x and y
    else if (type == 2)
    {
         
        // If x and y have different roots then
        // union them
        if (areSame(arr, x, y) == false)
            weighted_union(arr, rank, x, y);
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    // No.of nodes
    int n = 7;
 
    // The following two arrays are used to
    // implement disjoint set data structure.
    // arr[] holds the parent nodes while rank
    // array holds the rank of subset
    int []arr = new int[n];
    int []rank = new int[n];
 
    // initializing both array and rank
    for (int i = 0; i < n; i++)
    {
        arr[i] = i;
        rank[i] = 1;
    }
 
    // number of queries
    query(1, 0, 1, arr, rank);
    query(2, 0, 1, arr, rank);
    query(2, 1, 2, arr, rank);
    query(1, 0, 2, arr, rank);
    query(2, 0, 2, arr, rank);
    query(2, 2, 3, arr, rank);
    query(2, 3, 4, arr, rank);
    query(1, 0, 5, arr, rank);
    query(2, 4, 5, arr, rank);
    query(2, 5, 6, arr, rank);
    query(1, 2, 6, arr, rank);
}
}
 
// This code is contributed by PrinciRaj1992

No
Yes
No
Yes

Complejidad de tiempo:
la complejidad de tiempo amortizada es O (alfa (n)) por operación, donde alfa es la función de Ackermann inversa que es casi constante.

Este artículo es una contribución de Ayush Jha . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks. O(alfa(n))