Dado un árbol n-ario de n vértices y n-1 aristas. El árbol se da en forma de lista de adyacencia. Encuentre el número de subárboles de tamaño par en un árbol dado.
Ejemplos:
Input :
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
Output : 2
Subtree rooted at 1 and 3 are of even size.
Input :
1
/ \
2 3
/ | \ \
4 5 6 7
/ | \
8 9 10
Output : 3
Subtree rooted at 1, 3 and 5 are of even size.
Una solución simple es realizar dfs comenzando desde cada Node y encontrar el tamaño del subárbol enraizado en ese Node. Si el tamaño es par, incremente el conteo. La complejidad temporal de la solución anterior es O(n 2 ).
Una mejor solución es realizar dfs individuales en un árbol dado. La idea es encontrar primero recursivamente el tamaño del subárbol de todos los Nodes secundarios, luego encontrar el tamaño del subárbol enraizado en el Node actual tomando la suma del tamaño de los subárboles de los Nodes secundarios e incrementar el conteo si el tamaño es par.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find number of subtrees of even size.
#include <bits/stdc++.h>
using namespace std;
// DFS function to traverse the tree and find
// number of even size subtree.
int dfs(vector<int> adj[], int n, int v, int& ans)
{
// Size of subtree is minimum possible 1 for
// leaf node.
int size = 1;
// Find size of subtree rooted at children nodes
// and add the size to current subtree size.
for (auto ele : adj[v]) {
size += dfs(adj, n, ele, ans);
}
// If size is even then increment count.
if (size % 2 == 0)
ans++;
return size;
}
// Driver code
int main()
{
int n;
n = 10;
vector<int> adj[n + 1];
/*
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
*/
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[3].push_back(6);
adj[5].push_back(7);
adj[5].push_back(8);
/*
1
/ \
2 3
/ | \ \
4 5 6 7
/ | \
8 9 10
*/
/*adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
adj[2].push_back(6);
adj[3].push_back(7);
adj[5].push_back(8);
adj[5].push_back(9);
adj[5].push_back(10);
*/
int ans = 0;
dfs(adj, n, 1, ans);
cout << ans;
return 0;
}
Java
// Java program to find number of
// subtrees of even size.
import java.io.*;
import java.util.*;
class GFG
{
public static int ans = 0;
// DFS function to traverse the tree and
// find number of even size subtree.
static int dfs(ArrayList<ArrayList<Integer>> adj,
int n,int v)
{
// Size of subtree is minimum possible 1
// for leaf node.
int size = 1;
// Find size of subtree rooted at children
// nodes and add the size to current
// subtree size.
for(int ele:adj.get(v))
{
size += dfs(adj, n, ele);
}
// If size is even then increment count.
if(size % 2 == 0)
{
ans++;
}
return size;
}
// Driver code
public static void main (String[] args)
{
int n;
n = 10;
ArrayList<ArrayList<Integer>> adj = new ArrayList<ArrayList<Integer> >();
for(int i = 0; i < n + 1; i++)
{
adj.add(new ArrayList<Integer>());
}
/*
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
*/
adj.get(1).add(2);
adj.get(1).add(3);
adj.get(2).add(4);
adj.get(2).add(5);
adj.get(3).add(6);
adj.get(5).add(7);
adj.get(5).add(8);
/*
1
/ \
2 3
/ | \ \
4 5 6 7
/ | \
8 9 10
*/
/*adj[1].Add(2);
adj[1].Add(3);
adj[2].Add(4);
adj[2].Add(5);
adj[2].Add(6);
adj[3].Add(7);
adj[5].Add(8);
adj[5].Add(9);
adj[5].Add(10);
*/
dfs(adj, n, 1);
System.out.println(ans);
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 program to find number # of subtrees of even size ans = 0 # DFS function to traverse the tree # and find number of even size subtree def dfs(adj, n, v): global ans # Size of subtree is minimum possible # 1 for leaf node. size = 1 # Find size of subtree rooted at # children nodes and add the size # to current subtree size. for ele in adj[v]: size += dfs(adj, n, ele) # If size is even then increment count. if (size % 2 == 0): ans += 1 return size # Driver code if __name__ == '__main__': n = 10 adj = [[] for i in range(n + 1)] # 1 # / \ # 2 3 # / \ \ # 4 5 6 # / \ # 7 8 adj[1].append(2) adj[1].append(3) adj[2].append(4) adj[2].append(5) adj[3].append(6) adj[5].append(7) adj[5].append(8) # 1 # / \ # 2 3 # / | \ \ # 4 5 6 7 # / | \ # 8 9 10 # # adj[1].append(2) # adj[1].append(3) # adj[2].append(4) # adj[2].append(5) # adj[2].append(6) # adj[3].append(7) # adj[5].append(8) # adj[5].append(9) # adj[5].append(10) # # ans = 0 dfs(adj, n, 1) print(ans) # This code is contributed by mohit kumar 29
C#
// C# program to find number of
// subtrees of even size.
using System;
using System.Collections;
class GFG{
// DFS function to traverse the tree and
// find number of even size subtree.
static int dfs(ArrayList []adj, int n,
int v, ref int ans)
{
// Size of subtree is minimum possible 1
// for leaf node.
int size = 1;
// Find size of subtree rooted at children
// nodes and add the size to current
// subtree size.
foreach(int ele in adj[v])
{
size += dfs(adj, n, ele, ref ans);
}
// If size is even then increment count.
if (size % 2 == 0)
ans++;
return size;
}
// Driver code
public static void Main(string []args)
{
int n;
n = 10;
ArrayList []adj = new ArrayList[n + 1];
for(int i = 0; i < n + 1; i++)
{
adj[i] = new ArrayList();
}
/*
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
*/
adj[1].Add(2);
adj[1].Add(3);
adj[2].Add(4);
adj[2].Add(5);
adj[3].Add(6);
adj[5].Add(7);
adj[5].Add(8);
/*
1
/ \
2 3
/ | \ \
4 5 6 7
/ | \
8 9 10
*/
/*adj[1].Add(2);
adj[1].Add(3);
adj[2].Add(4);
adj[2].Add(5);
adj[2].Add(6);
adj[3].Add(7);
adj[5].Add(8);
adj[5].Add(9);
adj[5].Add(10);
*/
int ans = 0;
dfs(adj, n, 1, ref ans);
Console.Write(ans);
}
}
// This code is contributed by rutvik_56
Javascript
<script>
// Javascript program to find number of subtrees of even size.
var ans = 0;
// DFS function to traverse the tree and find
// number of even size subtree.
function dfs(adj, n, v)
{
// Size of subtree is minimum possible 1 for
// leaf node.
var size = 1;
// Find size of subtree rooted at children nodes
// and add the size to current subtree size.
for(var i =0; i< adj[v].length; i++)
{
size += dfs(adj, n, adj[v][i]);
}
// If size is even then increment count.
if (size % 2 == 0)
ans++;
return size;
}
// Driver code
var n;
n = 10;
var adj = Array.from(Array(n+1), () => new Array(0))
/*
1
/ \
2 3
/ \ \
4 5 6
/ \
7 8
*/
adj[1].push(2);
adj[1].push(3);
adj[2].push(4);
adj[2].push(5);
adj[3].push(6);
adj[5].push(7);
adj[5].push(8);
/*
1
/ \
2 3
/ | \ \
4 5 6 7
/ | \
8 9 10
*/
/*adj[1].push(2);
adj[1].push(3);
adj[2].push(4);
adj[2].push(5);
adj[2].push(6);
adj[3].push(7);
adj[5].push(8);
adj[5].push(9);
adj[5].push(10);
*/
dfs(adj, n, 1);
document.write( ans);
// This code is contributed by noob2000.
</script>
Producción:
2
Complejidad temporal: O(n)
Espacio auxiliar: O(1)