C++ program to find ways to color a skewed tree such that parent and child have different colors














































C++ program to find ways to color a skewed tree such that parent and child have different colors



Executable on C++11/14/17

Description and Approach:

This is practically a Combinatorics problem. The approach here is very simple, The root node of the skewed tree can be coloured in k ways where k is the total number of colours available, and for every other node (i.e remaining N-1 nodes), it has K-1 choices of colours as it cannot have the same colour as it's parent. So total number of ways = K X (K-1)^(N-1).

*Note: Skewed tree ->every node has at most one child.

Implementation:

#include<bits/stdc++.h> using namespace std; //Function to calculate power efficiently long calc_power(long a, long b) { if( b == 0 ) return 1; long chk = calc_power( a, b>>1 ); if(b & 1) return a * chk * chk; else return chk * chk; } int main(int argc, char const *argv[]) { long n, colors; cout<<"Enter the number of nodes present in the skewed tree"<<endl; cin>>n; cout<<"enter the number of colours available (Must be > 1)"<<endl; cin>>colors; cout<<"The number of ways in which the skewed tree can be coloured is: "<<endl; cout<<colors*calc_power(colors-1, n-1)<<endl; return 0; }

Time Complexity: O(log2(n)), Efficient method of calculating power is done in log2(n) time.

Sample Output:
gs_katti@gsk-47534B:~/Desktop/CppSecret$ g++ 22.skewed_color.cpp
s_katti@gsk-47534B:~/Desktop/CppSecret$ ./a.out
Enter the number of nodes present in the skewed tree 5 enter the number of colours available (Must be > 1) 6 The number of ways in which the skewed tree can be coloured is: 3750


More Articles of GHANASHYAM KATTI:

Name Views Likes
C++ std::reverse with std::vector 658 24
C++ std::search with std::vector 613 15
C++ std::is_permutation with std::vector 664 20
C++ program to reverse a path in binary search tree using queue 695 17
C++ std::partial_sort with std::vector 609 23
C++ std::partition_point with vector 631 15
C++ std::partition_point with multiset 704 27
C++ program to calculate tilt of binary tree 507 16
C++ program to find right sibling of a binary tree with parent pointers 936 16
C++ program to find root of the tree where children id sum for every node is given 665 21
C++ std::count with std::vector 673 23
C++ std::mismatch with std::deque 605 26
C++ std::partial_sort with std::array 758 12
C++ program to remove nodes on root to leaf paths of length < k 521 20
C++ std::mismatch with std::array 950 15
C++ std::is_permutation with std::array 570 14
C++ std::nth_element with std::array 786 23
C++ std::count_if with std::list 687 15
C++ std::move_backward with std::deque 636 12
C++ std::mismatch with std::list 576 19
C++ std::move_backward with std::list 698 20
C++ std::random_shuffle with std::array 564 24
C++ std::mismatch with std::forward_list 552 19
C++ std::count with std::array 772 26
C++ program to find simple recursive solution to check whether binary search tree contains dead end 728 19
C++ program to find ways to color a skewed tree such that parent and child have different colors 681 28
C++ std::count_if with std::array 786 23
C++ program to find deepest left leaf node in a binary tree using recursion 456 20
C++ program to check if a given binary tree is sumtree 546 11
C++ program to calculate size of a tree using recursion 760 11
C++ program to transform a binary search tree to greater sum tree 493 14
C++ program to find longest path with same values in a binary tree 965 11
C++ program to find extract leaves of a binary tree in a doubly linked list 514 17
C++ program to find sum of nodes at k-th level in a tree represented as string 839 16
C++ std::count_if with std::multiset 740 17
C++ std::count with std::deque 1572 20
C++ program to find all duplicate subtrees 690 15
C++ program to find mirror of a given node in binary tree 603 26
C++ program to find deepest right leaf node in a binary tree using recursion 549 17
C++ std::mismatch with std::vector 626 19
C++ program to find maximum width of a binary tree 637 14
C++ std::partition_point with std::array 595 16
C++ program to find distance from root to given node in a binary tree 510 14
C++ program to find factor tree of a given number 1171 16
C++ std::partition_point with std::list 803 13
C++ std::reverse with std::deque 896 21
C++ program to remove all nodes which don%u2019t lie in any path with sum>= k 593 17
C++ std::count with std::list 559 11
C++ std::partition_point with std::deque 662 20
C++ std::count_if with std::deque 674 26
C++ std::partial_sort with std::deque 683 13
C++ std::mismatch with std::multiset 656 21
C++ std::search with std::deque 581 20
C++ std::partition_point with std::forward_list 578 14
C++ std::count_if with std::vector 811 16
C++ program to find largest subtree having identical left and right subtrees 546 14
C++ std::random_shuffle with std::deque 1099 15
C++ std::nth_element with std::vector 630 19
C++ std::move_backward with std::array 724 20
C++ program to find a number in minimum steps 597 23
C++ std::reverse with std::array 724 18
C++ std::random_shuffle with std::vector 632 14
C++ program to check if all leaves are at same level 490 15
C++ std::count with std::multiset 449 14
C++ program to connect nodes at same level 523 21
C++ std::move_backward with std::vector 658 20
C++ std::is_permutation with std::deque 530 13
C++ std::search with std::array 685 17
C++ std::nth_element with std::deque 1219 18
C++ program to find longest consecutive sequence in binary tree 565 11

Comments