计算给定树中权重为主要的节点

原文： https://www.geeksforgeeks.org/count-the-nodes-in-the-given-tree-whose-weight-is-prime/

给定一棵树，以及所有节点的权重，任务是计算权重为质数的节点的数量。

示例：

输入： 输出：2 仅节点 1 和 3 的权重为质数。

方法：在树上执行 dfs ，对于每个节点，检查其权重是否为素数。

下面是上述方法的实现：

C++

// C++ implementation of the approach 
#include <bits/stdc++.h> 
using namespace std; 

int ans = 0; 

vector<int> graph[100]; 
vector<int> weight(100); 

// Function that returns true 
// if n is prime 
bool isprime(int n) 
{ 
    for (int i = 2; i * i <= n; i++) 
        if (n % i == 0) 
            return false; 
    return true; 
} 

// Function to perform dfs 
void dfs(int node, int parent) 
{ 
    // If weight of node is prime or not 
    if (isprime(weight[node])) 
        ans += 1; 

    for (int to : graph[node]) { 
        if (to == parent) 
            continue; 
        dfs(to, node); 
    } 
} 

// Driver code 
int main() 
{ 
    // Weights of the node 
    weight[1] = 5; 
    weight[2] = 10; 
    weight[3] = 11; 
    weight[4] = 8; 
    weight[5] = 6; 

    // Edges of the tree 
    graph[1].push_back(2); 
    graph[2].push_back(3); 
    graph[2].push_back(4); 
    graph[1].push_back(5); 

    dfs(1, 1); 

    cout << ans; 

    return 0; 
}

Java

// Java implementation of the approach 
import java.util.*; 

class GFG{ 

static int ans = 0; 

static Vector<Integer>[] graph = new Vector[100];  
static int[] weight = new int[100]; 

// Function that returns true 
// if n is prime 
static boolean isprime(int n) 
{ 
    for (int i = 2; i * i <= n; i++) 
        if (n % i == 0) 
            return false; 
    return true; 
} 

// Function to perform dfs 
static void dfs(int node, int parent) 
{ 
    // If weight of node is prime or not 
    if (isprime(weight[node])) 
        ans += 1; 

    for (int to : graph[node]) { 
        if (to == parent) 
            continue; 
        dfs(to, node); 
    } 
} 

// Driver code 
public static void main(String[] args) 
{ 
    for (int i = 0; i < 100; i++)  
        graph[i] = new Vector<>(); 

    // Weights of the node 
    weight[1] = 5; 
    weight[2] = 10; 
    weight[3] = 11; 
    weight[4] = 8; 
    weight[5] = 6; 

    // Edges of the tree 
    graph[1].add(2); 
    graph[2].add(3); 
    graph[2].add(4); 
    graph[1].add(5); 

    dfs(1, 1); 

    System.out.print(ans);  
} 
} 

// This code is contributed by Rajput-Ji

Python

# Python3 implementation of the approach 
ans = 0

graph = [[] for i in range(100)] 
weight = [0] * 100

# Function that returns true 
# if n is prime 
def isprime(n): 
    i = 2
    while(i * i <= n): 
        if (n % i == 0): 
            return False
        i += 1
    return True

# Function to perform dfs 
def dfs(node, parent): 
    global ans 

    # If weight of the current node is even 
    if (isprime(weight[node])): 
        ans += 1; 

    for to in graph[node]: 
        if (to == parent): 
            continue
        dfs(to, node) 

# Driver code 

# Weights of the node 
weight[1] = 5
weight[2] = 10
weight[3] = 11
weight[4] = 8
weight[5] = 6

# Edges of the tree 
graph[1].append(2) 
graph[2].append(3) 
graph[2].append(4) 
graph[1].append(5) 

dfs(1, 1) 
print(ans) 

# This code is contributed by SHUBHAMSINGH10

C

// C# implementation of the approach  
using System;  
using System.Collections;  
using System.Collections.Generic;  
using System.Text;  

class GFG{ 

static int ans = 0;  
static ArrayList[] graph = new ArrayList[100];  
static int[] weight = new int[100];  

// Function that returns true 
// if n is prime 
static bool isprime(int n) 
{ 
    for(int i = 2; i * i <= n; i++) 
        if (n % i == 0) 
            return false; 

    return true; 
} 

// Function to perform dfs 
static void dfs(int node, int parent) 
{ 

    // If weight of node is prime or not 
    if (isprime(weight[node])) 
        ans += 1; 

    foreach(int to in graph[node]) 
    { 
        if (to == parent) 
            continue; 

        dfs(to, node); 
    } 
} 

// Driver Code 
public static void Main(string[] args) 
{ 
    for(int i = 0; i < 100; i++)  
        graph[i] = new ArrayList(); 

    // Weights of the node 
    weight[1] = 5; 
    weight[2] = 10; 
    weight[3] = 11; 
    weight[4] = 8; 
    weight[5] = 6; 

    // Edges of the tree 
    graph[1].Add(2); 
    graph[2].Add(3); 
    graph[2].Add(4); 
    graph[1].Add(5); 

    dfs(1, 1); 

    Console.Write(ans);  
} 
} 

// This code is contributed by rutvik_56

Output:

2

复杂度分析：

  • 时间复杂度：O（N * sqrt（V）），其中 V 是给定树中节点的最大权重。

    在 DFS 中，树的每个节点都处理一次，因此，当树中总共有 N 个节点时，由于 DFS 导致的复杂度为O(N)。 同样，在处理每个节点时，为了检查节点值是否为质数，正在运行一个高达 sqrt（V）的循环，其中 V 是节点的权重。 因此，对于每个节点，都会增加 O（sqrt（V））的复杂度。 因此，时间复杂度为 O（N * sqrt（V））。

  • 辅助空间：O(1)。

    不需要任何额外的空间，因此空间复杂度是恒定的。

如果您喜欢 GeeksforGeeks 并希望做出贡献，则还可以使用 tribution.geeksforgeeks.org 撰写文章，或将您的文章邮寄至 tribution@geeksforgeeks.org。 查看您的文章出现在 GeeksforGeeks 主页上，并帮助其他 Geeks。

如果您发现任何不正确的地方，请单击下面的“改进文章”按钮，以改进本文。

版权属于：月萌API www.moonapi.com，转载请注明出处

本文链接：https://moonapi.com/news/33281.html