Dado un árbol de N Nodes, la tarea es encontrar el número máximo de aristas que se pueden agregar al árbol para que se convierta en un gráfico bipartito .
Nota : no se permiten bucles automáticos o bordes múltiples, pero se permiten ciclos.
Ejemplos:
Entrada : N = 4, Aristas = {{1, 2}, {2, 3}, {1, 4}}
1
/ \
2 4
/
3
Salida : 1
Explicación : Se puede agregar una arista entre los Nodes 3 y 4 tal que el gráfico sigue siendo bipartito.
No se puede agregar más de 1 borde de modo que el gráfico resultante sea bipartito.Entrada: N = 5, Aristas = {{1, 2}, {1, 3}, {2, 4}, {2, 5}}
1
/ \
2 3
/ \
4 5
Salida : 2
Explicación : Dos aristas pueden agregarse, (3, 4) y (3, 5) y el gráfico sigue siendo bipartito.
Enfoque ingenuo: la forma básica de resolver el problema es la siguiente:
Asigne cada Node del árbol como negro o blanco, de modo que un Node negro esté conectado con un Node blanco (siempre existe esa configuración porque un árbol siempre es bipartito).
Luego, para todos los pares posibles de Nodes, verifique si se puede agregar un borde entre ellos.
Siga los pasos mencionados a continuación para implementar la idea anterior:
- Atraviese el árbol inicialmente y asigne cada Node como negro o blanco, de modo que cada borde conecte un Node negro y uno blanco. (Los árboles son siempre bipartitos ).
- Itere sobre todos los pares de Nodes y verifique si se puede agregar un borde entre ellos.
- Si ambos Nodes son de diferentes colores y no hay borde entre ellos, se puede agregar un borde. Así que incrementa el conteo .
- De lo contrario, no se puede agregar ningún borde.
- El valor final de count es la respuesta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// DFS to mark nodes as black or white.
void dfs(int node, int par, bool isBlack,
vector<vector<bool> >& adj,
vector<bool>& color)
{
// Mark color as black or white.
color[node] = isBlack;
for (int i = 1; i < adj.size(); ++i) {
// If there is no edge,
// or 'i' is parent, continue.
if (!adj[node][i] || i == par)
continue;
dfs(i, node, !isBlack, adj, color);
}
}
// Function to calculate
// maximum number of edges
// that can be added
long long maxEdges(int n,
vector<pair<int, int> > edges)
{
// Build adjacency matrix.
vector<vector<bool> > adj(n + 1,
vector<bool>(
n + 1, 0));
for (auto i : edges) {
adj[i.first][i.second] = 1;
adj[i.second][i.first] = 1;
}
// Call DFS to color nodes.
vector<bool> color(n + 1);
dfs(1, 0, 1, adj, color);
long long ans = 0;
// Iterate over all pairs of nodes.
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
// If the color is different
// And there is no edge
// Between them, increment answer.
if (color[i] != color[j]
&& !adj[i][j])
ans++;
}
}
// Return answer.
return ans;
}
// Driver Code
int main()
{
int N = 4;
vector<pair<int, int> > edges
= { { 1, 2 }, { 2, 3 }, { 1, 4 } };
cout << maxEdges(N, edges);
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main {
public static void main(String[] args)
{
int N = 4;
List<List<Integer> > edges = new ArrayList<>();
edges.add(Arrays.asList(1, 2));
edges.add(Arrays.asList(2, 3));
edges.add(Arrays.asList(1, 4));
System.out.println(maxEdges(N, edges));
}
// Function to calculate
// maximum number of edges
// that can be added
public static long maxEdges(int n,
List<List<Integer> > edges)
{
// Build adjacency matrix.
boolean[][] adj = new boolean[n + 1][n + 1];
for (int i = 0; i < edges.size(); ++i) {
adj[edges.get(i).get(0)][edges.get(i).get(1)]
= true;
adj[edges.get(i).get(1)][edges.get(i).get(0)]
= true;
}
// Call DFS to color nodes.
boolean[] color = new boolean[n + 1];
dfs(1, 0, true, adj, color);
long ans = 0;
// Iterate over all pairs of nodes.
for (int i = 1; i <= n; ++i) {
for (int j = i + 1; j <= n; ++j) {
// If the color is different
// And there is no edge
// Between them, increment answer.
if (color[i] != color[j] && !adj[i][j])
ans++;
}
}
// return ans
return ans;
}
// DFS to mark nodes as black or white.
public static void dfs(int node, int par,
boolean isBlack, boolean[][] adj,
boolean[] color)
{
// Mark color as black or white.
color[node] = isBlack;
for (int i = 1; i < adj.length; ++i)
{
// If there is no edge,
// or 'i' is parent, continue.
if (!adj[node][i] || i == par)
continue;
dfs(i, node, !isBlack, adj, color);
}
}
}
// This code is contributed by Tapesh(tapeshdua420)
Python3
# Python code for the above approach: # DFS to mark nodes as black or white. def dfs(node, par, isBlack, adj, color): # Mark color as black or white. color[node] = isBlack for i in range(1, len(adj)): # If there is no edge, # or 'i' is parent, continue. if not adj[node][i] or i == par: continue dfs(i, node, not isBlack, adj, color) # Function to calculate # maximum number of edges # that can be added def maxEdges(n, edges): # Build adjacency matrix. adj = [[0 for _ in range(n + 1)] for _ in range(n + 1)] for i in edges: adj[i[0]][i[1]] = 1 adj[i[1]][i[0]] = 1 # Call DFS to color nodes. color = [0 for _ in range(n + 1)] dfs(1, 0, 1, adj, color) ans = 0 # Iterate over all pairs of nodes. for i in range(1, n + 1): for j in range(i + 1, n + 1): # If the color is different # And there is no edge # Between them, increment answer. if color[i] != color[j] and not adj[i][j]: ans += 1 # Return answer. return ans # Driver Code N = 4 edges = [[1, 2], [2, 3], [1, 4]] print(maxEdges(N, edges)) # This code is contributed by tapeshdua420.
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
using System.Linq;
class Program {
static void Main(string[] args)
{
int N = 4;
List<Tuple<int, int> > edges
= new List<Tuple<int, int> >(N);
edges.Add(new Tuple<int, int>(1, 2));
edges.Add(new Tuple<int, int>(2, 3));
edges.Add(new Tuple<int, int>(1, 4));
Console.WriteLine(maxEdges(N, edges));
}
// DFS to mark nodes as black or white.
static void dfs(int node, int par, bool isBlack,
bool[, ] adj, bool[] color)
{
// Mark color as black or white.
color[node] = isBlack;
for (int i = 1; i < adj.GetLength(0); i++)
{
// If there is no edge,
// or 'i' is parent, continue.
if (adj[node, i] == false || i == par)
continue;
dfs(i, node, !isBlack, adj, color);
}
}
// Function to calculate
// maximum number of edges
// that can be added
static long maxEdges(int n,
List<Tuple<int, int> > edges)
{
// Build adjacency matrix.
bool[, ] adj = new bool[n + 1, n + 1];
foreach(Tuple<int, int> tuple in edges)
{
adj[tuple.Item1, tuple.Item2] = true;
adj[tuple.Item2, tuple.Item1] = true;
}
// Call DFS to color nodes.
bool[] color = new bool[n + 1];
dfs(1, 0, true, adj, color);
long ans = 0;
// Iterate over all pairs of nodes.
for (int i = 1; i <= n; ++i)
{
for (int j = i + 1; j <= n; ++j)
{
// If the color is different
// And there is no edge
// Between them, increment answer.
if (color[i] != color[j]
&& adj[i, j] == false)
ans++;
}
}
// Return answer.
return ans;
}
}
// This code is contributed by tapeshdua420.
Producción
1
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N 2 )
Enfoque eficiente: el tiempo empleado en el enfoque anterior se puede optimizar utilizando la siguiente observación:
Digamos que inicialmente había B Nodes negros y W Nodes blancos en el árbol. Entonces, un gráfico bipartito creado a partir de estos Nodes puede tener bordes B*W máximos.
Por lo tanto, el número máximo de aristas que se pueden agregar al árbol con N Nodes es B*W – (N-1) [ya que un árbol con N Nodes tiene N-1 aristas]
Siga los pasos que se mencionan a continuación:
- Atraviese el árbol inicialmente y asigne cada Node como negro o blanco, de modo que cada borde conecte un Node negro y uno blanco. (Los árboles son siempre bipartitos).
- Cuente el número de Nodes negros y Nodes blancos.
- Use la fórmula derivada de la observación anterior y calcule el número máximo de aristas que se pueden agregar.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code for the above approach:
#include <bits/stdc++.h>
using namespace std;
// DFS to count number of black nodes.
int dfs(int node, int par, bool isBlack,
vector<vector<int> >& adj)
{
int no_Of_Black = isBlack;
for (int i : adj[node]) {
if (i == par)
continue;
// Number of black nodes
// in each subtree.
no_Of_Black
+= dfs(i, node, !isBlack, adj);
}
return no_Of_Black;
}
// Function to find maximum edges
long long maxEdges(int n,
vector<pair<int, int> > edges)
{
// Build adjacency list.
vector<vector<int> > adj(n + 1);
for (auto i : edges) {
adj[i.first].push_back(i.second);
adj[i.second].push_back(i.first);
}
// Number of black nodes.
int no_Of_Black = dfs(1, 0, 1, adj);
// Number of white nodes.
int no_Of_White = n - no_Of_Black;
// Number of edges that can be added.
return (1LL * (no_Of_Black)
* (no_Of_White)
- (n - 1));
}
// Driver code
int main()
{
int N = 4;
vector<pair<int, int> > edges
= { { 1, 2 }, { 2, 3 }, { 1, 4 } };
cout << maxEdges(N, edges);
return 0;
}
Java
// Java code for the above approach:
import java.util.*;
public class Main
{
// Driver code
public static void main(String[] args)
{
int N = 4;
int[][] edges = { { 1, 2 }, { 2, 3 }, { 1, 4 } };
System.out.println(maxEdges(N, edges));
}
// Function to find maximum edges
public static long maxEdges(int n, int[][] edges)
{
// Build adjacency list.
List<List<Integer> > adj = new ArrayList<>();
for (int i = 0; i <= n; i++) {
adj.add(new ArrayList<>());
}
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
adj.get(edge[1]).add(edge[0]);
}
// Number of black nodes.
int no_Of_Black = dfs(1, 0, true, adj);
// Number of white nodes.
int no_Of_White = n - no_Of_Black;
// Number of edges that can be added.
return ((no_Of_Black) * (no_Of_White) - (n - 1));
}
// DFS to count number of black nodes.
public static int dfs(int node, int par,
boolean isBlack,
List<List<Integer> > adj)
{
int no_Of_Black = (isBlack == true) ? 1 : 0;
for (int i : adj.get(node)) {
if (i == par)
continue;
// Number of black nodes
// in each subtree.
no_Of_Black += dfs(i, node, !isBlack, adj);
}
return no_Of_Black;
}
}
// This code is contributed by Tapesh(tapeshdua420)
Python3
## DFS to count number of black nodes. def dfs(node, par, isBlack, adj) : no_of_black = isBlack for i in adj[node]: if(i==par): continue ## Number of black nodes ## in each subtree. no_of_black += dfs(i, node, (not isBlack), adj) return no_of_black def maxEdges(n, edges): adj = [] for i in range(n+1): adj.append(list()) ## Create the graph ## From the given input. for i in edges: adj[i[0]].append(i[1]) adj[i[1]].append(i[0]) ## Number of black nodes. no_of_black = dfs(1, 0, 1, adj) ## Number of white nodes. no_of_white = n - no_of_black ## Number of edges that can be added. return (no_of_black*no_of_white) - (n-1) # Driver Code if __name__ == "__main__": N = 4 edges = list((list((1, 2)), list((2, 3)), list((1, 4)))) print(maxEdges(N, edges)) # This code is contributed by subhamgoyal2014.
C#
// C# code for the above approach:
using System;
using System.Collections.Generic;
class Program {
// Driver code
static void Main(string[] args)
{
int N = 4;
int[][] edges
= { new int[] { 1, 2 }, new int[] { 2, 3 },
new int[] { 1, 4 } };
Console.WriteLine(maxEdges(N, edges));
}
// Function to find maximum edges
static long maxEdges(int n, int[][] edges)
{
// Build adjacency list.
List<List<int> > adj = new List<List<int> >();
for (int i = 0; i <= n; i++) {
adj.Add(new List<int>());
}
foreach(int[] edge in edges)
{
adj[edge[0]].Add(edge[1]);
adj[edge[1]].Add(edge[0]);
}
// Number of black nodes.
int no_Of_Black = dfs(1, 0, true, adj);
// Number of white nodes.
int no_Of_White = n - no_Of_Black;
// Number of edges that can be added.
return ((no_Of_Black) * (no_Of_White) - (n - 1));
}
// DFS to count number of black nodes.
static int dfs(int node, int par, bool isBlack,
List<List<int> > adj)
{
int no_Of_Black = (isBlack == true) ? 1 : 0;
foreach(int i in adj[node])
{
if (i == par)
continue;
// Number of black nodes
// in each subtree.
no_Of_Black += dfs(i, node, !isBlack, adj);
}
return no_Of_Black;
}
}
// This code is contributed by Tapesh (tapeshdua420)
Producción
1
Complejidad temporal: O(N)
Espacio auxiliar: O(N)