Número máximo de aristas que se agregarán a un árbol para que permanezca como un gráfico bipartito

Un árbol siempre es un gráfico bipartito , ya que siempre podemos dividirlo en dos conjuntos disjuntos con niveles alternos. En otras palabras, siempre lo coloreamos con dos colores de modo que los niveles alternos tengan el mismo color. La tarea es calcular el número máximo. de aristas que se pueden añadir al árbol para que siga siendo Gráfico bipartito. 

Ejemplos: 

Input : Tree edges as vertex pairs 
        1 2
        1 3
Output : 0
Explanation :
The only edge we can add is from node 2 to 3.
But edge 2, 3 will result in odd cycle, hence 
violation of Bipartite Graph property.

Input : Tree edges as vertex pairs 
        1 2
        1 3
        2 4
        3 5
Output : 2
Explanation : On colouring the graph, {1, 4, 5} 
and {2, 3} form two different sets. Since, 1 is 
connected from both 2 and 3, we are left with 
edges 4 and 5. Since, 4 is already connected to
2 and 5 to 3, only options remain {4, 3} and 
{5, 2}.

1. Realice un recorrido DFS (o BFS ) simple del gráfico y coloréelo con dos colores. 
2. Mientras colorea, también realice un seguimiento de los recuentos de Nodes coloreados con los dos colores. Sean los dos conteos count_color ₀ y count_color ₁ . 
3. Ahora sabemos que los bordes máximos que puede tener un gráfico bipartito son count_color ₀ x count_color ₁ . 
4. También sabemos que el árbol con n Nodes tiene n-1 aristas. 
5. Entonces nuestra respuesta es count_color ₀ x count_color ₁ – (n-1).

A continuación se muestra la implementación: 

// CPP code to print maximum edges such that
// Tree remains a Bipartite graph
#include <bits/stdc++.h>
using namespace std;
 
// To store counts of nodes with two colors
long long count_color[2];
 
void dfs(vector<int> adj[], int node, int parent, int color)
{
    // Increment count of nodes with current
    // color
    count_color[color]++;
 
    // Traversing adjacent nodes
    for (int i = 0; i < adj[node].size(); i++) {
 
        // Not recurring for the parent node
        if (adj[node][i] != parent)
            dfs(adj, adj[node][i], node, !color);
    }
}
 
// Finds maximum number of edges that can be added
// without violating Bipartite property.
int findMaxEdges(vector<int> adj[], int n)
{
    // Do a DFS to count number of nodes
    // of each color
    dfs(adj, 1, 0, 0);
 
    return count_color[0] * count_color[1] - (n - 1);
}
 
// Driver code
int main()
{
    int n = 5;
    vector<int> adj[n + 1];
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[3].push_back(5);
    cout << findMaxEdges(adj, n);
    return 0;
}

// Java code to print maximum edges such that
// Tree remains a Bipartite graph
import java.util.*;
 
class GFG
{
 
// To store counts of nodes with two colors
static long []count_color = new long[2];
 
static void dfs(Vector<Integer> adj[], int node,
                      int parent, boolean color)
{
    // Increment count of nodes with current
    // color
    count_color[color == false ? 0 : 1]++;
 
    // Traversing adjacent nodes
    for (int i = 0; i < adj[node].size(); i++)
    {
 
        // Not recurring for the parent node
        if (adj[node].get(i) != parent)
            dfs(adj, adj[node].get(i), node, !color);
    }
}
 
// Finds maximum number of edges that can be added
// without violating Bipartite property.
static int findMaxEdges(Vector<Integer> adj[], int n)
{
    // Do a DFS to count number of nodes
    // of each color
    dfs(adj, 1, 0, false);
 
    return (int) (count_color[0] *
                  count_color[1] - (n - 1));
}
 
// Driver code
public static void main(String[] args)
{
    int n = 5;
    Vector<Integer>[] adj = new Vector[n + 1];
    for (int i = 0; i < n + 1; i++)
        adj[i] = new Vector<Integer>();
     
    adj[1].add(2);
    adj[1].add(3);
    adj[2].add(4);
    adj[3].add(5);
    System.out.println(findMaxEdges(adj, n));
}
}
 
// This code is contributed by Rajput-Ji

# Python 3 code to print maximum edges such
# that Tree remains a Bipartite graph
def dfs(adj, node, parent, color):
     
    # Increment count of nodes with
    # current color
    count_color[color] += 1
 
    # Traversing adjacent nodes
    for i in range(len(adj[node])):
 
        # Not recurring for the parent node
        if (adj[node][i] != parent):
            dfs(adj, adj[node][i],
                         node, not color)
 
# Finds maximum number of edges that
# can be added without violating
# Bipartite property.
def findMaxEdges(adj, n):
     
    # Do a DFS to count number of
    # nodes of each color
    dfs(adj, 1, 0, 0)
 
    return (count_color[0] *
            count_color[1] - (n - 1))
 
# Driver code
 
# To store counts of nodes with
# two colors
count_color = [0, 0]
n = 5
adj = [[] for i in range(n + 1)]
adj[1].append(2)
adj[1].append(3)
adj[2].append(4)
adj[3].append(5)
print(findMaxEdges(adj, n))
 
# This code is contributed by PranchalK

// C# code to print maximum edges such that
// Tree remains a Bipartite graph
using System;
using System.Collections.Generic;
 
class GFG
{
 
// To store counts of nodes with two colors
static long []count_color = new long[2];
 
static void dfs(List<int> []adj, int node,
                     int parent, bool color)
{
    // Increment count of nodes with current
    // color
    count_color[color == false ? 0 : 1]++;
 
    // Traversing adjacent nodes
    for (int i = 0; i < adj[node].Count; i++)
    {
 
        // Not recurring for the parent node
        if (adj[node][i] != parent)
            dfs(adj, adj[node][i], node, !color);
    }
}
 
// Finds maximum number of edges that can be added
// without violating Bipartite property.
static int findMaxEdges(List<int> []adj, int n)
{
    // Do a DFS to count number of nodes
    // of each color
    dfs(adj, 1, 0, false);
 
    return (int) (count_color[0] *
                  count_color[1] - (n - 1));
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 5;
    List<int> []adj = new List<int>[n + 1];
    for (int i = 0; i < n + 1; i++)
        adj[i] = new List<int>();
     
    adj[1].Add(2);
    adj[1].Add(3);
    adj[2].Add(4);
    adj[3].Add(5);
    Console.WriteLine(findMaxEdges(adj, n));
}
}
 
// This code is contributed by PrinciRaj1992

<script>
    // Javascript code to print maximum edges such that
    // Tree remains a Bipartite graph
     
    // To store counts of nodes with two colors
    let count_color = new Array(2);
    count_color.fill(0);
 
    function dfs(adj, node, parent, color)
    {
        // Increment count of nodes with current
        // color
        count_color[color == false ? 0 : 1]++;
 
        // Traversing adjacent nodes
        for (let i = 0; i < adj[node].length; i++)
        {
 
            // Not recurring for the parent node
            if (adj[node][i] != parent)
                dfs(adj, adj[node][i], node, !color);
        }
    }
 
    // Finds maximum number of edges that can be added
    // without violating Bipartite property.
    function findMaxEdges(adj, n)
    {
        // Do a DFS to count number of nodes
        // of each color
        dfs(adj, 1, 0, false);
 
        return (count_color[0] * count_color[1] - (n - 1));
    }
     
    let n = 5;
    let adj = [];
    for (let i = 0; i < n + 1; i++)
        adj.push([]);
       
    adj[1].push(2);
    adj[1].push(3);
    adj[2].push(4);
    adj[3].push(5);
    document.write(findMaxEdges(adj, n));
 
// This code is contributed by suresh07.
</script>

2

Complejidad de tiempo: O(n)

Este artículo es una contribución de Rohit Thapliyal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.