http://www.geeksforgeeks.org/largest-independent-set-problem/
1
#include <iostream>
2
#include <vector>
3
#include <algorithm>
4
#include <queue>
5
#include <stack>
6
#include <
string
>
7
#include <fstream>
8
#include <map>
9
using
namespace
std;
10
11
struct
node {
12
int
data;
13
struct
node *left, *
right;
14
node() : data(
0
), left(NULL), right(NULL) { }
15
node(
int
d) : data(d), left(NULL), right(NULL) { }
16
};
17
18
int
LISS(node *
root) {
19
if
(!root)
return
0
;
20
int
sum =
1
;
21
if
(root->left) sum += LISS(root->left->left) + LISS(root->left->
right);
22
if
(root->right) sum += LISS(root->right->left) + LISS(root->right->
right);
23
return
max(sum, LISS(root->left) + LISS(root->
right));
24
}
25
26
int
main() {
27
node *root =
new
node(
20
);
28
root->left =
new
node(
8
);
29
root->right =
new
node(
22
);
30
root->left->left =
new
node(
4
);
31
root->left->right =
new
node(
12
);
32
root->left->right->left =
new
node(
10
);
33
root->left->right->right =
new
node(
14
);
34
root->right->right =
new
node(
25
);
35
cout <<
LISS(root);
36
return
0
;
37
}
