Dado un grafo con N vértices numerados de 0 a (N-1) y una array aristas[][] que representan las aristas del grafo, la tarea es encontrar el número máximo de pares que se pueden formar donde cada elemento de un par pertenece a diferentes componentes conexas del gráfico.
Ejemplos:
Entrada: N = 4, aristas = {{1, 2}, {2, 3}}
Salida: 3
Explicación: Total de Nodes 4 (de 0 a 3).
Hay 3 pares posibles: {0, 1}, {0, 2} y {0, 3}.
No hay par entre {1, 2} o {1, 3} o {2, 3} porque pertenecen a la misma componente conexa.
gráfico con bordes dados
Entrada: N = 2, aristas = {0, 1}
Salida: 0
Explicación: Todos los elementos pertenecen a la misma componente conexa.
Enfoque: el problema se puede resolver contando el número de componentes conectados y el número de Nodes en cada componente conectado. Se puede formar un total de N*(N-1)/2 Nodes a partir de los N Nodes dados. Pero, para obtener el número requerido de pares, reste el número de pares que se pueden formar entre los Nodes de cada componente conectado. Siga los pasos que se mencionan a continuación:
- Iniciar total como el número total de pares posibles que es N*(N-1)/2 .
- Use DFS para encontrar los diferentes componentes conectados y para cada componente:
- Averigüe la cantidad de Nodes en ese componente conectado y guárdelo en una variable (por ejemplo, cnt ).
- Reste el número de pares que estos Nodes pueden formar entre sí, es decir, cnt*(cnt – 1)/2 .
- Después de visitar todos los Nodes, el valor restante del total es la respuesta final.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// DFS function
void dfs(vector<int> adj[], int src,
bool visited[], int& cnt)
{
visited[src] = true;
// Count number of nodes
// in current component
cnt++;
for (auto it : adj[src]) {
if (!visited[it]) {
dfs(adj, it, visited, cnt);
}
}
}
// Function to count total possible pairs
int maxPairs(int N,
vector<vector<int> >& edges)
{
vector<int> adj[N];
// Building the adjacency matrix
for (int i = 0; i < edges.size(); i++) {
adj[edges[i][0]].push_back(
edges[i][1]);
adj[edges[i][1]].push_back(
edges[i][0]);
}
// Maximum total pairs
int total = N * (N - 1) / 2;
// Array to keep track of components
bool visited[N + 1] = { false };
// Loop to count total possible pairs
for (int i = 0; i < N; i++) {
if (visited[i] == false) {
int cnt = 0;
dfs(adj, i, visited, cnt);
// Subtract pairs from
// the same connected component
total -= (cnt * (cnt - 1) / 2);
}
}
return total;
}
// Driver code
int main()
{
int N = 4;
vector<vector<int> > edges = { { 1, 2 },
{ 2, 3 } };
int result = maxPairs(N, edges);
cout << result;
return 0;
}
Java
import java.io.*;
import java.util.*;
class GFG {
static int count = 0;
// DFS function
public static void
dfs(ArrayList<ArrayList<Integer> > adj, int src,
boolean visited[])
{
visited[src] = true;
// Count number of nodes
// in current component
count++;
for (int it : adj.get(src)) {
if (!visited[it]) {
dfs(adj, it, visited);
}
}
}
// Function to count total possible pairs
public static int
maxPairs(int N, ArrayList<ArrayList<Integer> > edges)
{
ArrayList<ArrayList<Integer> > adj
= new ArrayList<ArrayList<Integer> >();
for (int i = 0; i < N; i++) {
ArrayList<Integer> temp
= new ArrayList<Integer>();
adj.add(temp);
}
// Building the adjacency matrix
for (int i = 0; i < edges.size(); i++) {
ArrayList<Integer> temp
= adj.get(edges.get(i).get(0));
temp.add(edges.get(i).get(1));
adj.set(edges.get(i).get(0), temp);
temp = adj.get(edges.get(i).get(1));
temp.add(edges.get(i).get(0));
adj.set(edges.get(i).get(1), temp);
}
// Maximum total pairs
int total = N * (N - 1) / 2;
// Array to keep track of components
boolean[] visited = new boolean[N + 1];
for (int i = 0; i <= N; i++) {
visited[i] = false;
}
// Loop to count total possible pairs
for (int i = 0; i < N; i++) {
if (visited[i] == false) {
count = 0;
dfs(adj, i, visited);
// Subtract pairs from
// the same connected component
total -= (count * (count - 1) / 2);
}
}
return total;
}
// Driver code
public static void main(String[] args)
{
int N = 4;
ArrayList<ArrayList<Integer> > edges
= new ArrayList<ArrayList<Integer> >();
edges.add(
new ArrayList<Integer>(Arrays.asList(1, 2)));
edges.add(
new ArrayList<Integer>(Arrays.asList(2, 3)));
int result = maxPairs(N, edges);
System.out.println(result);
}
}
// This code is contributed by Palak Gupta
Python3
# python3 code to implement the approach visited = [] cnt = 0 # DFS function def dfs(adj, src): global visited global cnt visited[src] = True # Count number of nodes # in current component cnt += 1 for it in adj[src]: if (not visited[it]): dfs(adj, it) # Function to count total possible pairs def maxPairs(N, edges): global visited global cnt adj = [[] for _ in range(N)] # Building the adjacency matrix for i in range(0, len(edges)): adj[edges[i][0]].append(edges[i][1]) adj[edges[i][1]].append(edges[i][0]) # Maximum total pairs total = (N * (N - 1)) // 2 # Array to keep track of components for i in range(N + 1): visited.append(False) # Loop to count total possible pairs for i in range(0, N): if (visited[i] == False): cnt = 0 dfs(adj, i) # Subtract pairs from # the same connected component total -= ((cnt * (cnt - 1)) // 2) return total # Driver code if __name__ == "__main__": N = 4 edges = [[1, 2], [2, 3]] result = maxPairs(N, edges) print(result) # This code is contributed by rakeshsahni
C#
using System;
using System.Collections.Generic;
class GFG
{
static int count = 0;
// DFS function
public static void
dfs(List<List<int>> adj, int src, bool[] visited)
{
visited[src] = true;
// Count number of nodes
// in current component
count++;
foreach (int it in adj[src])
{
if (!visited[it])
{
dfs(adj, it, visited);
}
}
}
// Function to count total possible pairs
public static int
maxPairs(int N, List<List<int>> edges)
{
List<List<int>> adj = new List<List<int>>();
for (int i = 0; i < N; i++)
{
List<int> temp = new List<int>();
adj.Add(temp);
}
// Building the adjacency matrix
for (int i = 0; i < edges.Count; i++)
{
List<int> temp = adj[edges[i][0]];
temp.Add(edges[i][1]);
adj[edges[i][0]] = temp;
temp = adj[edges[i][1]];
temp.Add(edges[i][0]);
adj[edges[i][1]] = temp;
}
// Maximum total pairs
int total = N * (N - 1) / 2;
// Array to keep track of components
bool[] visited = new bool[N + 1];
for (int i = 0; i <= N; i++)
{
visited[i] = false;
}
// Loop to count total possible pairs
for (int i = 0; i < N; i++)
{
if (visited[i] == false)
{
count = 0;
dfs(adj, i, visited);
// Subtract pairs from
// the same connected component
total -= (count * (count - 1) / 2);
}
}
return total;
}
// Driver code
public static void Main()
{
int N = 4;
List<List<int>> edges = new List<List<int>>();
edges.Add(new List<int>());
edges.Add(new List<int>());
edges[0].Add(1);
edges[0].Add(2);
edges[1].Add(2);
edges[1].Add(3);
int result = maxPairs(N, edges);
Console.Write(result);
}
}
// This code is contributed by Saurabh Jaiswal
Javascript
<script>
// JavaScript code for the above approach
// DFS function
function dfs(adj, src,
visited, cnt) {
visited[src] = true;
// Count number of nodes
// in current component
cnt++;
for (let it of adj[src]) {
if (!visited[it]) {
dfs(adj, it, visited, cnt);
}
}
return cnt;
}
// Function to count total possible pairs
function maxPairs(N,
edges) {
let adj = new Array(N).fill([]);
// Building the adjacency matrix
for (let i = 0; i < edges.length; i++) {
adj[edges[i][0]].push(
edges[i][1]);
adj[edges[i][1]].push(
edges[i][0]);
}
// Maximum total pairs
let total = N * (N - 1) / 2;
// Array to keep track of components
let visited = new Array(N + 1).fill(false)
// Loop to count total possible pairs
for (let i = 0; i < N; i++) {
if (visited[i] == false) {
let cnt = 0;
dfs(adj, i, visited, cnt);
// Subtract pairs from
// the same connected component
total -= (cnt * (cnt - 1) / 2);
}
}
return total / 2;
}
// Driver code
let N = 4;
let edges = [[1, 2],
[2, 3]];
let result = maxPairs(N, edges);
document.write(result);
// This code is contributed by Potta Lokesh
</script>
Producción
3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por bansalashish2101 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA