Dado un árbol que consiste en N Nodes valorados en el rango [0, N) y una array Consultas [] de Q enteros que consisten en valores en el rango [0, N) . La tarea de cada consulta es eliminar el vértice valorado Q[i] y contar los componentes conectados en el gráfico resultante.
Ejemplos:
Entrada: N = 7, Bordes[][2] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}} , Consultas[] = {0, 1, 6}
Salida:
3 3 1
Explicación:
Consulta 1: La eliminación del Node valorado en 0 conduce a la eliminación de los bordes (0, 1), (0, 2) y (0, 3). Por lo tanto, el gráfico restante tiene 3 componentes conectados: [1, 4, 5], [2], [3, 6]
Consulta 2: La eliminación del Node valorado en 1 conduce a la eliminación de los bordes (1, 4), (1 , 5) y (1, 0). Por lo tanto, el gráfico restante tiene 3 componentes conectados: [4], [5], [2, 0, 3, 6]
Consulta 3: La eliminación del Node valorado en 6 conduce a la eliminación de los bordes (3, 6). Por lo tanto, el gráfico restante tiene 1 componente conexa: [0, 1, 2, 3, 4, 5].Entrada: N = 7, Bordes[][2] = {{0, 1}, {0, 2}, {0, 3}, {1, 4}, {1, 5}, {3, 6}} , Consultas[] = {5, 3, 2}
Salida: 1 2 1
Explicación:
Consulta 1: La eliminación del Node valorado en 5 conduce a la eliminación del borde (1, 5). Por lo tanto, el gráfico restante tiene 1 componente conexa: [0, 1, 2, 3, 4, 6]
Consulta 2: La eliminación del Node valorado en 3 conduce a la eliminación de los bordes (0, 3), (3, 6). Por lo tanto, el gráfico restante tiene 2 componentes conectados: [0, 1, 2, 4, 5], [6]
Consulta 3: La eliminación del Node valorado en 2 conduce a la eliminación del borde (0, 2). Por lo tanto, el gráfico restante tiene 1 componente conexa: [0, 1, 3, 4, 5, 6]
Planteamiento: La idea es observar que en un Árbol , cada vez que se elimina un Node, los Nodes que estaban conectados entre sí a ese Node se separan. Entonces, el recuento de componentes conectados se vuelve igual al grado del Node eliminado .
Por lo tanto, el enfoque es precalcular y almacenar el grado de cada Node en una array. Para cada consulta, el recuento de los componentes conectados es simplemente el grado del Node correspondiente en la consulta.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
#define MAX 100005
// Stores degree of the nodes
int degree[MAX];
// Function that finds the degree of
// each node in the given graph
void DegreeOfNodes(int Edges[][2],
int N)
{
// Precompute degrees of each node
for (int i = 0; i < N - 1; i++) {
degree[Edges[i][0]]++;
degree[Edges[i][1]]++;
}
}
// Function to print the number of
// connected components
void findConnectedComponents(int x)
{
// Print the degree of node x
cout << degree[x] << ' ';
}
// Function that counts the connected
// components after removing a vertex
// for each query
void countCC(int N, int Q, int Queries[],
int Edges[][2])
{
// Count degree of each node
DegreeOfNodes(Edges, N);
// Iterate over each query
for (int i = 0; i < Q; i++) {
// Find connected components
// after removing given vertex
findConnectedComponents(Queries[i]);
}
}
// Driver Code
int main()
{
// Given N nodes and Q queries
int N = 7, Q = 3;
// Given array of queries
int Queries[] = { 0, 1, 6 };
// Given Edges
int Edges[][2] = { { 0, 1 }, { 0, 2 },
{ 0, 3 }, { 1, 4 },
{ 1, 5 }, { 3, 6 } };
// Function Call
countCC(N, Q, Queries, Edges);
return 0;
}
Java
// Java program for
// the above approach
import java.util.*;
class GFG{
static final int MAX = 100005;
// Stores degree of the nodes
static int []degree = new int[MAX];
// Function that finds the degree of
// each node in the given graph
static void DegreeOfNodes(int [][]Edges,
int N)
{
// Precompute degrees of each node
for (int i = 0; i < N - 1; i++)
{
degree[Edges[i][0]]++;
degree[Edges[i][1]]++;
}
}
// Function to print the number of
// connected components
static void findConnectedComponents(int x)
{
// Print the degree of node x
System.out.print(degree[x] + " ");
}
// Function that counts the connected
// components after removing a vertex
// for each query
static void countCC(int N, int Q,
int Queries[],
int [][]Edges)
{
// Count degree of each node
DegreeOfNodes(Edges, N);
// Iterate over each query
for (int i = 0; i < Q; i++)
{
// Find connected components
// after removing given vertex
findConnectedComponents(Queries[i]);
}
}
// Driver Code
public static void main(String[] args)
{
// Given N nodes and Q queries
int N = 7, Q = 3;
// Given array of queries
int Queries[] = {0, 1, 6};
// Given Edges
int [][]Edges = {{0, 1}, {0, 2},
{0, 3}, {1, 4},
{1, 5}, {3, 6}};
// Function Call
countCC(N, Q, Queries, Edges);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program for the above approach MAX = 100005 # Stores degree of the nodes degree = [0] * MAX # Function that finds the degree of # each node in the given graph def DegreeOfNodes(Edges, N): # Precompute degrees of each node for i in range(N - 1): degree[Edges[i][0]] += 1 degree[Edges[i][1]] += 1 # Function to print the number of # connected components def findConnectedComponents(x): # Print the degree of node x print(degree[x], end = " ") # Function that counts the connected # components after removing a vertex # for each query def countCC(N, Q, Queries, Edges): # Count degree of each node DegreeOfNodes(Edges, N) # Iterate over each query for i in range(Q): # Find connected components # after removing given vertex findConnectedComponents(Queries[i]) # Driver Code if __name__ == '__main__': # Given N nodes and Q queries N = 7 Q = 3 # Given array of queries Queries = [ 0, 1, 6 ] # Given Edges Edges = [ [ 0, 1 ], [ 0, 2 ], [ 0, 3 ], [ 1, 4 ], [ 1, 5 ], [ 3, 6 ] ] # Function call countCC(N, Q, Queries, Edges) # This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
class GFG{
static readonly int MAX = 100005;
// Stores degree of the nodes
static int []degree = new int[MAX];
// Function that finds the degree of
// each node in the given graph
static void DegreeOfNodes(int [,]Edges,
int N)
{
// Precompute degrees of each node
for (int i = 0; i < N - 1; i++)
{
degree[Edges[i, 0]]++;
degree[Edges[i, 1]]++;
}
}
// Function to print the number of
// connected components
static void findConnectedComponents(int x)
{
// Print the degree of node x
Console.Write(degree[x] + " ");
}
// Function that counts the connected
// components after removing a vertex
// for each query
static void countCC(int N, int Q,
int []Queries,
int [,]Edges)
{
// Count degree of each node
DegreeOfNodes(Edges, N);
// Iterate over each query
for (int i = 0; i < Q; i++)
{
// Find connected components
// after removing given vertex
findConnectedComponents(Queries[i]);
}
}
// Driver Code
public static void Main(String[] args)
{
// Given N nodes and Q queries
int N = 7, Q = 3;
// Given array of queries
int []Queries = {0, 1, 6};
// Given Edges
int [,]Edges = {{0, 1}, {0, 2},
{0, 3}, {1, 4},
{1, 5}, {3, 6}};
// Function Call
countCC(N, Q, Queries, Edges);
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// Javascript program for the above approach
var MAX = 100005
// Stores degree of the nodes
var degree = Array(MAX).fill(0)
// Function that finds the degree of
// each node in the given graph
function DegreeOfNodes(Edges, N)
{
// Precompute degrees of each node
for (var i = 0; i < N - 1; i++) {
degree[Edges[i][0]]++;
degree[Edges[i][1]]++;
}
}
// Function to print the number of
// connected components
function findConnectedComponents(x)
{
// Print the degree of node x
document.write( degree[x] + ' ');
}
// Function that counts the connected
// components after removing a vertex
// for each query
function countCC(N, Q, Queries, Edges)
{
// Count degree of each node
DegreeOfNodes(Edges, N);
// Iterate over each query
for (var i = 0; i < Q; i++) {
// Find connected components
// after removing given vertex
findConnectedComponents(Queries[i]);
}
}
// Driver Code
// Given N nodes and Q queries
var N = 7, Q = 3;
// Given array of queries
var Queries = [ 0, 1, 6 ];
// Given Edges
var Edges = [ [ 0, 1 ], [ 0, 2 ],
[ 0, 3 ], [ 1, 4 ],
[ 1, 5 ], [ 3, 6 ] ];
// Function Call
countCC(N, Q, Queries, Edges);
</script>
3 3 1
Complejidad de tiempo: O(E + Q), donde E es el número de aristas (E = N – 1) y Q es el número de consultas.
Espacio Auxiliar: O(V), donde V es el número de vértices.