Dado un árbol que consta de N Nodes numerados a partir de [1, N] y está coloreado de negro (indicado por 1) o verde (indicado por 0) , la tarea es contar el número de secuencias de longitud K [a 1 , a 2 , ..a K ] tal que el camino tomado entre Nodes consecutivos es el más corto y los bordes cubiertos consisten en al menos un borde negro. Como la respuesta puede ser grande, imprímela en módulo de 10 9 +7 .
Entrada: N = 4, K = 4
1-2 0
2-3 0
2-4 0
Salida: 0
Explicación:
Ya que no hay borde negro en el árbol. No hay tales secuencias.Entrada: N = 3, K = 3
1-2 1
2-3 1
Salida: 24
Explicación:
Todas las 3 3 secuencias excepto (1, 1, 1), (2, 2, 2) y (3, 3, 3) están incluidos en la respuesta.
Enfoque:
La idea es contar el número de secuencias de longitud K de modo que no se cubra ningún borde negro. Deje que la cuenta sea temp . Entonces (N K ) – temp es la respuesta requerida. La temperatura se puede calcular fácilmente eliminando los bordes negros y luego calculando el tamaño de los diferentes componentes del gráfico resultante.
Siga los pasos a continuación:
- Inicialice el valor de ans como N K .
- Construya un gráfico G agregando solo bordes verdes.
- Realice un recorrido DFS del gráfico y siga restando (tamaño K ) del ans donde el tamaño es el número de Nodes en diferentes componentes del gráfico G.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the
// above approach
#include <bits/stdc++.h>
#define int long long int
using namespace std;
const int mod = 1e9 + 7;
const int N = 1e5 + 1;
// Vector to store the graph
vector<int> G[N];
// Iterative Function to calculate
// (a<sup>b</sup>) % mod in O(log b)
int power(int a, int b) {
// Initialize result
int res = 1;
// Update x if it is more than
// or equal to p
a = a % mod;
if (a == 0)
// In case x is divisible by p;
return 0;
while (b > 0) {
// If a is odd,
// multiply x with result
if (b & 1)
res = (res * a) % mod;
// b must be even now
b = b >> 1; // b = b/2
a = (a * a) % mod;
}
return res;
}
// DFS traversal of the nodes
void dfs(int i, int& size,
bool* visited) {
// Mark the current
// node as visited
visited[i] = true;
// Increment the size of the
// current component
size++;
// Recur for all the vertices
// adjacent to this node
for (auto nbr : G[i]) {
if (!visited[nbr]) {
dfs(nbr, size, visited);
}
}
}
// Function to calculate the
// final answer
void totalSequences(int& ans,
int n, int k)
{
// Mark all the vertices as
// not visited initially
bool visited[n + 1];
memset(visited, false,
sizeof(visited));
// Subtract (size^k) from the answer
// for different components
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
int size = 0;
dfs(i, size, visited);
ans -= power(size, k);
ans += mod;
ans = ans % mod;
}
}
}
// Function to add edges to the graph
void addEdge(int x, int y, int color)
{
// If the colour is green,
// include it in the graph
if (color == 0) {
G[x].push_back(y);
G[y].push_back(x);
}
}
int32_t main()
{
// Number of node in the tree
int n = 3;
// Size of sequence
int k = 3;
// Initialize the result as n^k
int ans = power(n, k);
/* 2
/ \
1 3
Let us create binary tree as shown
in above example */
addEdge(1, 2, 1);
addEdge(2, 3, 1);
totalSequences(ans, n, k);
cout << ans << endl;
}
Java
// Java implementation of the
// above approach
import java.util.*;
class GFG{
static int mod = (int)(1e9 + 7);
static int N = (int)(1e5 + 1);
static int size;
static int ans;
// Vector to store the graph
@SuppressWarnings("unchecked")
static Vector<Integer> []G = new Vector[N];
// Iterative Function to calculate
// (a<sup>b</sup>) % mod in O(log b)
static int power(int a, int b)
{
// Initialize result
int res = 1;
// Update x if it is more than
// or equal to p
a = a % mod;
if (a == 0)
// In case x is divisible by p;
return 0;
while (b > 0)
{
// If a is odd,
// multiply x with result
if (b % 2 == 1)
res = (res * a) % mod;
// b must be even now
b = b >> 1; // b = b/2
a = (a * a) % mod;
}
return res;
}
// DFS traversal of the nodes
static void dfs(int i, boolean []visited)
{
// Mark the current
// node as visited
visited[i] = true;
// Increment the size of the
// current component
size++;
// Recur for all the vertices
// adjacent to this node
for(int nbr : G[i])
{
if (!visited[nbr])
{
dfs(nbr, visited);
}
}
}
// Function to calculate the
// final answer
static void totalSequences(int n, int k)
{
// Mark all the vertices as
// not visited initially
boolean []visited = new boolean[n + 1];
// Subtract (size^k) from the answer
// for different components
for(int i = 1; i <= n; i++)
{
if (!visited[i])
{
size = 0;
dfs(i, visited);
ans -= power(size, k);
ans += mod;
ans = ans % mod;
}
}
}
// Function to add edges to the graph
static void addEdge(int x, int y, int color)
{
// If the colour is green,
// include it in the graph
if (color == 0)
{
G[x].add(y);
G[y].add(x);
}
}
// Driver code
public static void main(String[] args)
{
for(int i = 0; i < G.length; i++)
G[i] = new Vector<Integer>();
// Number of node in the tree
int n = 3;
// Size of sequence
int k = 3;
// Initialize the result as n^k
ans = power(n, k);
/* 2
/ \
1 3
Let us create binary tree as shown
in above example */
addEdge(1, 2, 1);
addEdge(2, 3, 1);
totalSequences(n, k);
System.out.print(ans + "\n");
}
}
// This code is contributed by Amit Katiyar
Python3
# Python3 program for the above approach mod = 1e9 + 7 N = 1e5 + 1 # List to store the graph G = [0] * int(N) # Iterative Function to calculate # (a<sup>b</sup>) % mod in O(log b) def power(a, b): # Initialize result res = 1 # Update x if it is more than # or equal to p a = a % mod if a == 0: # In case x is divisible by p; return 0 while b > 0: # If a is odd, # multiply x with result if b & 1: res = (res * a) % mod # b must be even now b = b >> 1 # b = b/2 a = (a * a) % mod return res # DFS traversal of the nodes def dfs(i, size, visited): # Mark the current # node as visited visited[i] = True # Increment the size of the # current component size[0] += 1 # Recur for all the vertices # adjacent to this node for nbr in range(G[i]): if not visited[nbr]: dfs(nbr, size, visited) # Function to calculate the # final answer def totalSequences(ans, n, k): # Mark all the vertices as # not visited initially visited = [False] * (n + 1) # Subtract (size^k) from the answer # for different components for i in range(1, n + 1): if not visited[i]: size = [0] dfs(i, size, visited) ans[0] -= power(size[0], k) ans[0] += mod ans[0] = ans[0] % mod # Function to add edges to the graph def addEdge(x, y, color): # If the colour is green, # include it in the graph if color == 0: G[x].append(y) G[y].append(x) # Driver code if __name__ == '__main__': # Number of node in the tree n = 3 # Size of sequence k = 3 # Initialize the result as n^k ans = [power(n, k)] """ 2 / \ 1 3 Let us create binary tree as shown in above example """ addEdge(1, 2, 1) addEdge(2, 3, 1) totalSequences(ans, n, k) print(int(ans[0])) # This code is contributed by Shivam Singh
C#
// C# implementation of the
// above approach
using System;
using System.Collections.Generic;
class GFG{
static int mod = (int)(1e9 + 7);
static int N = (int)(1e5 + 1);
static int size;
static int ans;
// List to store the graph
static List<int> []G =
new List<int>[N];
// Iterative Function to
// calculate (a<sup>b</sup>)
// % mod in O(log b)
static int power(int a,
int b)
{
// Initialize result
int res = 1;
// Update x if it is
// more than or equal
// to p
a = a % mod;
if (a == 0)
// In case x is
// divisible by p;
return 0;
while (b > 0)
{
// If a is odd,
// multiply x
// with result
if (b % 2 == 1)
res = (res * a) % mod;
// b must be even now
// b = b/2
b = b >> 1;
a = (a * a) % mod;
}
return res;
}
// DFS traversal of the nodes
static void dfs(int i,
bool []visited)
{
// Mark the current
// node as visited
visited[i] = true;
// Increment the size of the
// current component
size++;
// Recur for all the vertices
// adjacent to this node
foreach(int nbr in G[i])
{
if (!visited[nbr])
{
dfs(nbr, visited);
}
}
}
// Function to calculate the
// readonly answer
static void totalSequences(int n,
int k)
{
// Mark all the vertices as
// not visited initially
bool []visited = new bool[n + 1];
// Subtract (size^k) from the
// answer for different components
for(int i = 1; i <= n; i++)
{
if (!visited[i])
{
size = 0;
dfs(i, visited);
ans -= power(size, k);
ans += mod;
ans = ans % mod;
}
}
}
// Function to add edges
// to the graph
static void addEdge(int x,
int y,
int color)
{
// If the colour is green,
// include it in the graph
if (color == 0)
{
G[x].Add(y);
G[y].Add(x);
}
}
// Driver code
public static void Main(String[] args)
{
for(int i = 0; i < G.Length; i++)
G[i] = new List<int>();
// Number of node
// in the tree
int n = 3;
// Size of sequence
int k = 3;
// Initialize the
// result as n^k
ans = power(n, k);
/* 2
/ \
1 3
Let us create binary tree
as shown in above example */
addEdge(1, 2, 1);
addEdge(2, 3, 1);
totalSequences(n, k);
Console.Write(ans + "\n");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript implementation of the above approach
let mod = (1e9 + 7);
let N = (1e5 + 1);
let size;
let ans;
// List to store the graph
let G = new Array(N);
// Iterative Function to
// calculate (a<sup>b</sup>)
// % mod in O(log b)
function power(a, b)
{
// Initialize result
let res = 1;
// Update x if it is
// more than or equal
// to p
a = a % mod;
if (a == 0)
// In case x is
// divisible by p;
return 0;
while (b > 0)
{
// If a is odd,
// multiply x
// with result
if (b % 2 == 1)
res = (res * a) % mod;
// b must be even now
// b = b/2
b = b >> 1;
a = (a * a) % mod;
}
return res;
}
// DFS traversal of the nodes
function dfs(i, visited)
{
// Mark the current
// node as visited
visited[i] = true;
// Increment the size of the
// current component
size++;
// Recur for all the vertices
// adjacent to this node
for(let nbr = 0; nbr < G[i].length; nbr++)
{
if (!visited[G[i][nbr]])
{
dfs(G[i][nbr], visited);
}
}
}
// Function to calculate the
// readonly answer
function totalSequences(n, k)
{
// Mark all the vertices as
// not visited initially
let visited = new Array(n + 1);
visited.fill(false);
// Subtract (size^k) from the
// answer for different components
for(let i = 1; i <= n; i++)
{
if (!visited[i])
{
size = 0;
dfs(i, visited);
ans -= power(size, k);
ans += mod;
ans = ans % mod;
}
}
}
// Function to add edges
// to the graph
function addEdge(x, y, color)
{
// If the colour is green,
// include it in the graph
if (color == 0)
{
G[x].push(y);
G[y].push(x);
}
}
for(let i = 0; i < G.length; i++)
G[i] = [];
// Number of node
// in the tree
let n = 3;
// Size of sequence
let k = 3;
// Initialize the
// result as n^k
ans = power(n, k);
/* 2
/ \
1 3
Let us create binary tree
as shown in above example */
addEdge(1, 2, 1);
addEdge(2, 3, 1);
totalSequences(n, k);
document.write(ans + "</br>");
</script>
Producción:
24
Complejidad de tiempo: O (N), dado que el recorrido DFS requiere O (vértices + bordes) == O (N + (N-1)) == O (N) ) complejidad.
Publicación traducida automáticamente
Artículo escrito por mohitkumarbt2k18 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA