Encontrar astronautas de diferentes países.

Dado un número entero positivo N que denota el número de astronautas (etiquetado de 0 a partir de (N – 1) ) y una array mat[][] que contiene los pares de astronautas que son del mismo país, la tarea es contar el número de formas elegir dos astronautas de diferentes países.

Ejemplos:

Entrada: N = 6, mat[][] = {{0, 1}, {0, 2}, {2, 5}}
Salida: 9
Explicación:
Los astronautas con ID {0, 1, 2, 5} pertenecen a primer país, el astronauta con ID {3} pertenece al segundo país y el astronauta con ID {4} pertenece al tercer país. El número de formas de elegir dos astronautas de diferentes países es:

1. Elige 1 astronauta del país 1 y 1 astronauta del país 2, luego el número total de formas es 4*1 = 4.
2. Elija 1 astronauta del país 1 y 1 astronauta del país 3, entonces el número total de formas es 4*1 = 4.
3. Elija 1 astronauta del país 2 y 1 astronauta del país 3, entonces el número total de formas es 1*1 = 1.

Por lo tanto, el número total de formas es 4 + 4 + 1 = 9. 

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

Enfoque: El problema dado se puede resolver modelando este problema como un gráfico en el que los astronautas representan los vértices del gráfico y los pares dados representan los bordes del gráfico. Después de construir el gráfico, la idea es calcular el número de formas de seleccionar 2 astronautas de diferentes países. Siga los pasos para resolver el problema:

• Cree una lista de listas, adj[][] para almacenar la lista de adyacencia del gráfico .
• Recorra la array dada arr[] usando la variable i y agregue arr[i][1] a adj[arr[i][0]] y también agregue arr[i][0] a adj[arr[i][1 ]] para el borde no dirigido.
• Ahora encuentre el tamaño de cada componente conectado del gráfico realizando la búsqueda en profundidad primero , usando el enfoque discutido en este artículo, y almacene todos los tamaños de los componentes conectados en una array, digamos v[] .
• Inicialice una variable entera, digamos ans como el número total de formas de elegir 2 astronautas de N astronautas, es decir, N*(N – 1)/2 .
• Recorra la array v[] y reste v[i]*(v[i] – 1)/2 de la variable ans para excluir todos los pares posibles entre cada componente conectado.
• Después de completar los pasos anteriores, imprima el valor de ans 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;
 
// Function to perform the DFS Traversal
// to find the count of connected
// components
void dfs(int v, vector<vector<int> >& adj,
         vector<bool>& visited, int& num)
{
    // Marking vertex visited
    visited[v] = true;
    num++;
 
    // DFS call to neighbour vertices
    for (int i = 0; i < adj[v].size(); i++) {
 
        // If the current node is not
        // visited, then recursively
        // call DFS
        if (!visited[adj[v][i]]) {
            dfs(adj[v][i], adj,
                visited, num);
        }
    }
}
 
// Function to find the number of ways
// to choose two astronauts from the
// different countries
void numberOfPairs(
    int N, vector<vector<int> > arr)
{
    // Stores the Adjacency list
    vector<vector<int> > adj(N);
 
    // Constructing the graph
    for (vector<int>& i : arr) {
        adj[i[0]].push_back(i[1]);
        adj[i[1]].push_back(i[0]);
    }
 
    // Stores the visited vertices
    vector<bool> visited(N);
 
    // Stores the size of every
    // connected components
    vector<int> v;
 
    int num = 0;
    for (int i = 0; i < N; i++) {
 
        if (!visited[i]) {
 
            // DFS call to the graph
            dfs(i, adj, visited, num);
 
            // Store size of every
            // connected component
            v.push_back(num);
            num = 0;
        }
    }
 
    // Stores the total number of
    // ways to count the pairs
    int ans = N * (N - 1) / 2;
 
    // Traverse the array
    for (int i : v) {
        ans -= (i * (i - 1) / 2);
    }
 
    // Print the value of ans
    cout << ans;
}
 
// Driver Code
int main()
{
    int N = 6;
    vector<vector<int> > arr = { { 0, 1 }, { 0, 2 }, { 2, 5 } };
    numberOfPairs(N, arr);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
public class GFG
{
    // Function to perform the DFS Traversal
    // to find the count of connected
    // components
    static Vector<Vector<Integer>> adj;
    static boolean[] visited;
    static int num;
     
    // Function to perform the DFS Traversal
    // to find the count of connected
    // components
    static void dfs(int v)
    {
       
        // Marking vertex visited
        visited[v] = true;
        num++;
   
        // DFS call to neighbour vertices
        for (int i = 0; i < adj.get(v).size(); i++) {
   
            // If the current node is not
            // visited, then recursively
            // call DFS
            if (!visited[adj.get(v).get(i)]) {
                dfs(adj.get(v).get(i));
            }
        }
    }
   
    // Function to find the number of ways
    // to choose two astronauts from the
    // different countries
    static void numberOfPairs(int N, int[][] arr)
    {
        // Stores the Adjacency list
        adj = new Vector<Vector<Integer>>();
        for(int i = 0; i < N; i++)
        {
            adj.add(new Vector<Integer>());
        }
   
        // Constructing the graph
        for (int i = 0; i < 2; i++) {
            adj.get(arr[i][0]).add(arr[i][1]);
            adj.get(arr[i][1]).add(arr[i][0]);
        }
   
        // Stores the visited vertices
        visited = new boolean[N];
        Arrays.fill(visited, false);
   
        // Stores the size of every
        // connected components
        Vector<Integer> v = new Vector<Integer>();
   
        num = 0;
        for (int i = 0; i < N; i++) {
   
            if (!visited[i]) {
   
                // DFS call to the graph
                dfs(i);
   
                // Store size of every
                // connected component
                v.add(num);
                num = 0;
            }
        }
   
        // Stores the total number of
        // ways to count the pairs
        int ans = N * (N - 1) / 2 + 1;
   
        // Traverse the array
        for (int i = 0; i < v.size(); i++) {
            ans -= (v.get(i) * (v.get(i) - 1) / 2) +1;
        }
   
        // Print the value of ans
        System.out.print(ans);
    }
     
    public static void main(String[] args) {
        int N = 6;
        int[][] arr = { { 0, 1 }, { 0, 2 }, { 2, 5 } };
        numberOfPairs(N, arr);
    }
}
 
// This code is contributed by suresh07

# Python3 program for the above approach
 
# Function to perform the DFS Traversal
# to find the count of connected
# components
adj = []
visited = []
num = 0
  
def dfs(v):
    global adj, visited, num
     
    # Marking vertex visited
    visited[v] = True
    num+=1
 
    # DFS call to neighbour vertices
    for i in range(len(adj[v])):
       
        # If the current node is not
        # visited, then recursively
        # call DFS
        if (not visited[adj[v][i]]):
            dfs(adj[v][i])
 
# Function to find the number of ways
# to choose two astronauts from the
# different countries
def numberOfPairs(N, arr):
    global adj, visited, num
    # Stores the Adjacency list
    adj = []
    for i in range(N):
        adj.append([])
 
    # Constructing the graph
    for i in range(len(arr)):
        adj[arr[i][0]].append(arr[i][1])
        adj[arr[i][1]].append(arr[i][0])
 
    # Stores the visited vertices
    visited = [False]*(N)
 
    # Stores the size of every
    # connected components
    v = []
 
    num = 0
    for i in range(N):
        if (not visited[i]):
            # DFS call to the graph
            dfs(i)
 
            # Store size of every
            # connected component
            v.append(num)
            num = 0
 
    # Stores the total number of
    # ways to count the pairs
    ans = N * int((N - 1) / 2)
 
    # Traverse the array
    for i in range(len(v)):
        ans -= (v[i] * int((v[i] - 1) / 2))
    ans+=1
 
    # Print the value of ans
    print(ans)
 
N = 6
arr = [ [ 0, 1 ], [ 0, 2 ], [ 2, 5 ] ]
numberOfPairs(N, arr)
 
# This code is contributed by mukesh07.

// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
     
    // Function to perform the DFS Traversal
    // to find the count of connected
    // components
    static List<List<int>> adj;
    static bool[] visited;
    static int num;
     
    // Function to perform the DFS Traversal
    // to find the count of connected
    // components
    static void dfs(int v)
    {
        // Marking vertex visited
        visited[v] = true;
        num++;
  
        // DFS call to neighbour vertices
        for (int i = 0; i < adj[v].Count; i++) {
  
            // If the current node is not
            // visited, then recursively
            // call DFS
            if (!visited[adj[v][i]]) {
                dfs(adj[v][i]);
            }
        }
    }
  
    // Function to find the number of ways
    // to choose two astronauts from the
    // different countries
    static void numberOfPairs(int N, int[,] arr)
    {
        // Stores the Adjacency list
        adj = new List<List<int>>();
        for(int i = 0; i < N; i++)
        {
            adj.Add(new List<int>());
        }
  
        // Constructing the graph
        for (int i = 0; i < 2; i++) {
            adj[arr[i,0]].Add(arr[i,1]);
            adj[arr[i,1]].Add(arr[i,0]);
        }
  
        // Stores the visited vertices
        visited = new bool[N];
        Array.Fill(visited, false);
  
        // Stores the size of every
        // connected components
        List<int> v = new List<int>();
  
        num = 0;
        for (int i = 0; i < N; i++) {
  
            if (!visited[i]) {
  
                // DFS call to the graph
                dfs(i);
  
                // Store size of every
                // connected component
                v.Add(num);
                num = 0;
            }
        }
  
        // Stores the total number of
        // ways to count the pairs
        int ans = N * (N - 1) / 2 + 1;
  
        // Traverse the array
        for (int i = 0; i < v.Count; i++) {
            ans -= (v[i] * (v[i] - 1) / 2) +1;
        }
  
        // Print the value of ans
        Console.Write(ans);
    }
     
  static void Main() {
    int N = 6;
    int[,] arr = { { 0, 1 }, { 0, 2 }, { 2, 5 } };
    numberOfPairs(N, arr);
  }
}
 
// This code is contributed by divyesh072019.

<script>
    // Javascript program for the above approach 
     
    // Function to perform the DFS Traversal
    // to find the count of connected
    // components
     
    let adj;
    let visited;
    let num;
     
    function dfs(v)
    {
        // Marking vertex visited
        visited[v] = true;
        num++;
 
        // DFS call to neighbour vertices
        for (let i = 0; i < adj[v].length; i++) {
 
            // If the current node is not
            // visited, then recursively
            // call DFS
            if (!visited[adj[v][i]]) {
                dfs(adj[v][i]);
            }
        }
    }
 
    // Function to find the number of ways
    // to choose two astronauts from the
    // different countries
    function numberOfPairs(N, arr)
    {
        // Stores the Adjacency list
        adj = [];
        for(let i = 0; i < N; i++)
        {
            adj.push([]);
        }
 
        // Constructing the graph
        for (let i = 0; i < arr.length; i++) {
            adj[arr[i][0]].push(arr[i][1]);
            adj[arr[i][1]].push(arr[i][0]);
        }
 
        // Stores the visited vertices
        visited = new Array(N);
        visited.fill(false);
 
        // Stores the size of every
        // connected components
        let v = [];
 
        num = 0;
        for (let i = 0; i < N; i++) {
 
            if (!visited[i]) {
 
                // DFS call to the graph
                dfs(i);
 
                // Store size of every
                // connected component
                v.push(num);
                num = 0;
            }
        }
 
        // Stores the total number of
        // ways to count the pairs
        let ans = N * (N - 1) / 2;
 
        // Traverse the array
        for (let i = 0; i < v.length; i++) {
            ans -= (v[i] * (v[i] - 1) / 2);
        }
 
        // Print the value of ans
        document.write(ans);
    }
     
    let N = 6;
    let arr = [ [ 0, 1 ], [ 0, 2 ], [ 2, 5 ] ];
    numberOfPairs(N, arr);
 
// This code is contributed by rameshtravel07.
</script>

9

Complejidad temporal: O(N + E), donde N es el número de vértices y E es el número de aristas.
Espacio Auxiliar: O(N + E)