Q:

Given a tree, you have to find out the largest independent set. Independent elements are those that don’t have any common edges. Print the length of the largest independent set

0

Largest Independent Set Problem

Given a tree, you have to find out the largest independent set. Independent elements are those that don’t have any common edges. Print the length of the largest independent set.

T Test case
T no. of input string will be given to you.

E.g.
2

Largest Independent Set Problem (1)

Largest Independent Set Problem (2) Output: Print the length of the largest Independent set.

Example

T=2

Input:
Largest Independent Set Problem (1)

Output:
5 ( 1,4,7,8,6)

Input:
Largest Independent Set Problem (2)

Output:
4 (3,2,6,7)

Explanation with example:

To find out the length of the independent set we have to consider every node in our consideration.

  • A node with its grandchildren are in the set
  • The child nodes are in the set.

Independent set of node(x) = max⁡ (1+independent set of its grandchildren,independent set of its children)

Example:

Largest Independent Set Problem (1)
In that case,
    Independent set of the node(1) = 
        max ⁡( independent set of node(4), node(5) and node(6)+1 , 
        independent set of the node(2)and node(3)

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

Recursive algorithm:

Function(Node):
    if(node==NULL)
        return 0
    excluding_the_node=Function(node->left)+Function(node->right)
    including_the_node=1
    if(node->left)
        including_the_node+=Function(node->left->left)+Function(node->left->right)
    if(node->right)
        including_the_node+=Function(node->right->left)+Function(node->right->right)
    return max(including_the_node,excluding_the_node)

DP conversion:

Function(Node):
    if(node==NULL)
        return 0
    if(vis[node])
        return vis[node]
    excluding_the_node=Function(node->left)+Function(node->right)
    including_the_node=1
    if(node->left)
        including_the_node+=Function(node->left->left)+Function(node->left->right)
    if(node->right)
        including_the_node+=Function(node->right->left)+Function(node->right->right)
    return vis[node]=max(including_the_node,excluding_the_node)

C++ Implementation:

#include <bits/stdc++.h>
using namespace std;

struct tree {
    int val, value;
    tree* left;
    tree* right;
};

struct tree* make_node(int x)
{
    tree* t = new tree;
    t->val = x;
    t->value = 0;
    t->left = t->right = NULL;
    return t;
}

int set_count(tree* t)
{
    if (t == NULL) {
        return 0;
    }
    if (t->value) {
        return t->value;
    }
    int excluding = set_count(t->left) + set_count(t->right);
    int including = 1;
    if (t->left)
        including += set_count(t->left->left) + set_count(t->left->right);
    if (t->right)
        including += set_count(t->right->left) + set_count(t->right->right);
    return max(excluding, including);
}

int main()
{

    tree* t = NULL;
    t = make_node(10);
    t->left = make_node(20);
    t->right = make_node(30);
    t->left->left = make_node(40);
    t->left->right = make_node(50);
    t->right->right = make_node(60);
    t->right->left = make_node(90);
    t->left->right->left = make_node(70);
    t->left->right->right = make_node(80);

    cout << "Max set count : " << set_count(t) << endl;
    
    return 0;
}

Output

Max set count : 6

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

interview C++ coding problems/challenges | dynamic programming

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now
Given a sequence of numbers you have to find out t... >>
<< A list of n days is given to you and there are thr...