Vértice más pequeño en las componentes conexas de todos los vértices en un gráfico indirecto dado

Dado un gráfico no dirigido G(V, E)  que consta de 2 N vértices y M aristas, la tarea es encontrar el vértice más pequeño en el componente conexo del vértice i para todos los valores de i en el rango [1, N] .

Ejemplos:

Entrada: N = 5, aristas[] = {{1, 2}, {2, 3}, {4, 5}}
Salida: 1 1 1 4 4
Explicación: El gráfico dado se puede dividir en un conjunto de dos componentes, es decir, {1, 2, 3} y {4, 5}.

1. Para i = 1, el vértice 1 pertenece a la componente {1, 2, 3}. Por lo tanto, el vértice mínimo en el conjunto es 1.
2. Para i = 2, el vértice 2 pertenece a la componente {1, 2, 3}. Por lo tanto, el vértice mínimo en el conjunto es 1.
3. Para i = 3, el vértice 3 pertenece a la componente {1, 2, 3}. Por lo tanto, el vértice mínimo en el conjunto es 1.
4. Para i = 4, el vértice 4 pertenece a la componente {4, 5}. Por lo tanto, el vértice mínimo en el conjunto es 4.
5. Para i = 5, el vértice 5 pertenece a la componente {4, 5}. Por lo tanto, el vértice mínimo en el conjunto es 4.

Entrada: N = 6, bordes[] = {{1, 3}, {2, 4}}
Salida: 1 2 1 2 5 6

Enfoque: El problema dado se puede resolver de manera eficiente con la ayuda de Disjoint Set Union . Se puede observar que los vértices conectados por una arista se pueden unir en el mismo conjunto y se puede usar un mapa desordenado para llevar la cuenta del vértice más pequeño de cada uno de los conjuntos formados. A continuación se detallan los pasos a seguir:

• Implemente las funciones find_set y union_set de Disjoint Set Union mediante el enfoque que se describe en este artículo, donde find_set(x) devuelve el número de conjunto que contiene x y union_set(x, y) une el conjunto que contiene x con el conjunto que contiene y .
• Recorre la array dada edge [] y para cada borde (u, v) , une el conjunto que contiene u con el conjunto que contiene v .
• Cree un mapa desordenado minVal , donde minVal[x] almacena el vértice mínimo del conjunto que contiene x como elemento.
• Itere sobre todos los vértices usando una variable i y para cada vértice establezca el valor de minVal[find_set(node ​​i)] al mínimo de minVal[find_set(i)] e i .
• Después de completar los pasos anteriores, para cada vértice, i en el rango [1, N] , imprima el valor de minVal[find_set(i)] como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
const int maxn = 100;
 
// Stores the parent and size of the
// set of the ith element
int parent[maxn], Size[maxn];
 
// Function to initialize the ith set
void make_set(int v)
{
    parent[v] = v;
    Size[v] = 1;
}
 
// Function to find set of ith vertex
int find_set(int v)
{
    // Base Case
    if (v == parent[v]) {
        return v;
    }
 
    // Recursive call to find set
    return parent[v] = find_set(
               parent[v]);
}
 
// Function to unite the set that includes
// a and the set that includes b
void union_sets(int a, int b)
{
    a = find_set(a);
    b = find_set(b);
 
    // If a and b are not from same set
    if (a != b) {
        if (Size[a] < Size[b])
            swap(a, b);
        parent[b] = a;
        Size[a] += Size[b];
    }
}
 
// Function to find the smallest vertex in
// the connected component of the ith
// vertex for all i in range [1, N]
void findMinVertex(
    int N, vector<pair<int, int> > edges)
{
    // Loop to initialize the ith set
    for (int i = 1; i <= N; i++) {
        make_set(i);
    }
 
    // Loop to unite all vertices connected
    // by edges into the same set
    for (int i = 0; i < edges.size(); i++) {
        union_sets(edges[i].first,
                   edges[i].second);
    }
 
    // Stores the minimum vertex value
    // for ith set
    unordered_map<int, int> minVal;
 
    // Loop to iterate over all vertices
    for (int i = 1; i <= N; i++) {
 
        // If current vertex does not exist
        // in minVal initialize it with i
        if (minVal[find_set(i)] == 0) {
            minVal[find_set(i)] = i;
        }
 
        // Update the minimum value of
        // the set having the ith vertex
        else {
            minVal[find_set(i)]
                = min(minVal[find_set(i)], i);
        }
    }
 
    // Loop to print required answer
    for (int i = 1; i <= N; i++) {
        cout << minVal[find_set(i)] << " ";
    }
}
 
// Driver Code
int main()
{
    int N = 6;
    vector<pair<int, int> > edges
        = { { 1, 3 }, { 2, 4 } };
    findMinVertex(N, edges);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
public class Main {
 
    // Stores the parent and size of the
    // set of the ith element
    static int[] parent = new int[100];
    static int[] Size = new int[100];
   
    // Function to initialize the ith set
    static void make_set(int v)
    {
        parent[v] = v;
        Size[v] = 1;
    }
 
    // Function to find set of ith vertex
    static int find_set(int v)
    {
        // Base Case
        if (v == parent[v]) {
            return v;
        }
 
        // Recursive call to find set
        return parent[v] = find_set(parent[v]);
    }
 
    // Function to unite the set that includes
    // a and the set that includes b
    static void union_sets(int a, int b)
    {
        a = find_set(a);
        b = find_set(b);
 
        // If a and b are not from same set
        if (a != b) {
            if (Size[a] < Size[b]) {
                int temp = a;
                a = b;
                b = temp;
            }
 
            parent[b] = a;
 
            Size[a] += Size[b];
        }
    }
    // Function to find the smallest vertex in
    // the connected component of the ith
    // vertex for all i in range [1, N]
    static void
    findMinVertex(int N,
                  ArrayList<ArrayList<Integer> > edges)
    {
        // Loop to initialize the ith set
        for (int i = 1; i <= N; i++) {
            make_set(i);
        }
        // Loop to unite all vertices connected
        // by edges into the same set
        for (int i = 0; i < edges.size(); i++) {
 
            union_sets(edges.get(i).get(0),
                       edges.get(i).get(1));
        }
 
        // Stores the minimum vertex value
        // for ith set
        Map<Integer, Integer> minVal = new HashMap<>();
        // Loop to iterate over all vertices
        for (int i = 1; i <= N; i++) {
            // If current vertex does not exist
            // in minVal initialize it with i
            if (!minVal.containsKey(find_set(i))) {
                minVal.put(find_set(i), i);
            }
            // Update the minimum value of
            // the set having the ith vertex
            else {
 
                minVal.put(
                    find_set(i),
                    Math.min((int)minVal.getOrDefault(
                                 (Integer)find_set(i), 0),
                             i));
            }
        }
        // Loop to print required answer
        for (int i = 1; i <= N; i++) {
            System.out.print(minVal.get(find_set(i)) + " ");
        }
    }
    // Driver Code
    public static void main(String[] args)
    {
        int N = 6;
        ArrayList<ArrayList<Integer> > edges
            = new ArrayList<ArrayList<Integer> >();
 
        ArrayList<Integer> a1 = new ArrayList<Integer>();
        a1.add(1);
        a1.add(3);
        edges.add(a1);
 
        ArrayList<Integer> a2 = new ArrayList<Integer>();
        a2.add(2);
        a2.add(4);
        edges.add(a2);
 
        findMinVertex(N, edges);
    }
}
 
// This code is contributed by Tapesh(tapeshdua420)

# Python 3 program for the above approach
 
maxn = 100
 
# Stores the parent and size of the
# set of the ith element
parent = [0]*maxn
Size = [0]*maxn
 
# Function to initialize the ith set
 
 
def make_set(v):
    parent[v] = v
    Size[v] = 1
 
# Function to find set of ith vertex
 
 
def find_set(v):
    # Base Case
    if (v == parent[v]):
        return v
 
    # Recursive call to find set
    parent[v] = find_set(
        parent[v])
    return parent[v]
 
# Function to unite the set that includes
# a and the set that includes b
 
 
def union_sets(a, b):
 
    a = find_set(a)
    b = find_set(b)
 
    # If a and b are not from same set
    if (a != b):
        if (Size[a] < Size[b]):
            a, b = b, a
        parent[b] = a
        Size[a] += Size[b]
 
# Function to find the smallest vertex in
# the connected component of the ith
# vertex for all i in range [1, N]
 
 
def findMinVertex(
        N, edges):
 
    # Loop to initialize the ith set
    for i in range(1, N + 1):
        make_set(i)
 
    # Loop to unite all vertices connected
    # by edges into the same set
    for i in range(len(edges)):
        union_sets(edges[i][0],
                   edges[i][1])
 
    # Stores the minimum vertex value
    # for ith set
    minVal = {}
 
    # Loop to iterate over all vertices
    for i in range(1, N + 1):
 
        # If current vertex does not exist
        # in minVal initialize it with i
        if (find_set(i) not in minVal):
            minVal[find_set(i)] = i
 
        # Update the minimum value of
        # the set having the ith vertex
        else:
            minVal[find_set(i)] = min(minVal[find_set(i)], i)
 
    # Loop to print required answer
    for i in range(1, N + 1):
        print(minVal[find_set(i)], end=" ")
 
# Driver Code
if __name__ == "__main__":
 
    N = 6
    edges = [[1, 3], [2, 4]]
    findMinVertex(N, edges)
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
using System.Collections.Generic;
using System.Linq;
 
class Program {
 
  // Stores the parent and size of the
  // set of the ith element
  static int[] parent = new int[100];
  static int[] Size = new int[100];
 
  // Function to initialize the ith set
  static void make_set(int v)
  {
    parent[v] = v;
    Size[v] = 1;
  }
 
  // Function to find set of ith vertex
  static int find_set(int v)
  {
    // Base Case
    if (v == parent[v]) {
      return v;
    }
 
    // Recursive call to find set
    return parent[v] = find_set(parent[v]);
  }
 
  // Function to unite the set that includes
  // a and the set that includes b
  static void union_sets(int a, int b)
  {
    a = find_set(a);
    b = find_set(b);
 
    // If a and b are not from same set
    if (a != b) {
      if (Size[a] < Size[b]) {
        int temp = a;
        a = b;
        b = temp;
      }
 
      parent[b] = a;
 
      Size[a] += Size[b];
    }
  }
 
  // Function to find the smallest vertex in
  // the connected component of the ith
  // vertex for all i in range [1, N]
  static void findMinVertex(int N, List<List<int> > edges)
  {
 
    // Loop to initialize the ith set
    for (int i = 1; i <= N; i++) {
      make_set(i);
    }
 
    // Loop to unite all vertices connected
    // by edges into the same set
    for (int i = 0; i < edges.Count(); i++) {
      union_sets(edges[i][0], edges[i][1]);
    }
 
    // Stores the minimum vertex value
    // for ith set
    Dictionary<int, int> minVal
      = new Dictionary<int, int>();
 
    // Loop to iterate over all vertices
    for (int i = 1; i <= N; i++) {
 
      // If current vertex does not exist
      // in minVal initialize it with i
      if (!minVal.ContainsKey(find_set(i))) {
        minVal.Add(find_set(i), i);
      }
      // Update the minimum value of
      // the set having the ith vertex
      else {
        minVal[find_set(i)] = Math.Min(
          (int)minVal.GetValueOrDefault(
            (int)find_set(i), 0),
          i);
      }
    }
 
    // Loop to print required answer
    for (int i = 1; i <= N; i++) {
 
      Console.Write("{0} ", minVal.GetValueOrDefault(
        (int)find_set(i), 0));
    }
  }
 
  // Driver Code
  public static void Main()
  {
 
    int N = 6;
    List<List<int> > edges = new List<List<int> >();
 
    List<int> a1 = new List<int>();
    a1.Add(1);
    a1.Add(3);
 
    edges.Add(a1);
 
    List<int> a2 = new List<int>();
    a2.Add(2);
    a2.Add(4);
    edges.Add(a2);
 
    findMinVertex(N, edges);
  }
}
 
// This code is contributed by tapeshdua420.

<script>
 
// JavaScript program for the above approach
const maxn = 100;
 
// Stores the parent and size of the
// set of the ith element
let parent = new Array(maxn);
let Size = new Array(maxn);
 
// Function to initialize the ith set
function make_set(v)
{
    parent[v] = v;
    Size[v] = 1;
}
 
// Function to find set of ith vertex
function find_set(v)
{
    // Base Case
    if (v == parent[v]) {
        return v;
    }
 
    // Recursive call to find set
    return parent[v] = find_set(parent[v]);
}
 
// Function to unite the set that includes
// a and the set that includes b
function union_sets(a, b)
{
    a = find_set(a);
    b = find_set(b);
 
    // If a and b are not from same set
    if (a != b) {
        if (Size[a] < Size[b]){
            let temp = a;
            a = b;
            b = temp;
        }
        parent[b] = a;
        Size[a] += Size[b];
    }
}
 
// Function to find the smallest vertex in
// the connected component of the ith
// vertex for all i in range [1, N]
function findMinVertex(N,edges)
{
    // Loop to initialize the ith set
    for (let i = 1; i <= N; i++) {
        make_set(i);
    }
 
    // Loop to unite all vertices connected
    // by edges into the same set
    for (let i = 0; i < edges.length; i++) {
        union_sets(edges[i][0],edges[i][1]);
    }
 
    // Stores the minimum vertex value
    // for ith set
    let minVal = new Map();
 
    // Loop to iterate over all vertices
    for (let i = 1; i <= N; i++) {
 
        // If current vertex does not exist
        // in minVal initialize it with i
        if (minVal.has(find_set(i)) == false) {
            minVal.set(find_set(i),i);
        }
 
        // Update the minimum value of
        // the set having the ith vertex
        else
        {
            minVal.set(find_set(i), Math.min(minVal.get(find_set(i)), i));
        }
    }
 
    // Loop to print required answer
    for (let i = 1; i <= N; i++) {
        document.write(minVal.get(find_set(i))," ");
    }
}
 
// Driver Code
let N = 6;
let edges = [ [ 1, 3 ], [ 2, 4 ] ];
findMinVertex(N, edges);
 
// This code is contributed by shinjanpatra
 
</script>

1 2 1 2 5 6

Complejidad temporal: O(N)
Espacio auxiliar: O(N)