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::partition_point with std::list 412 13
C++ std::partition_point with std::forward_list 332 14
C++ std::partition_point with multiset 407 27
C++ std::partition_point with std::array 367 16
C++ std::partition_point with std::deque 349 20
C++ std::partition_point with vector 309 15
C++ std::move_backward with std::list 360 20
C++ std::move_backward with std::deque 343 12
C++ std::move_backward with std::vector 341 20
C++ std::move_backward with std::array 286 20
C++ std::mismatch with std::forward_list 309 19
C++ std::mismatch with std::multiset 372 21
C++ std::mismatch with std::list 321 19
C++ std::mismatch with std::deque 355 26
C++ std::mismatch with std::vector 303 19
C++ std::mismatch with std::array 422 15
C++ std::partial_sort with std::array 356 12
C++ std::partial_sort with std::deque 283 13
C++ std::partial_sort with std::vector 324 23
C++ std::is_permutation with std::array 264 14
C++ std::is_permutation with std::vector 282 20
C++ std::is_permutation with std::deque 269 13
C++ std::reverse with std::deque 291 21
C++ std::reverse with std::vector 317 24
C++ std::reverse with std::array 281 18
C++ std::random_shuffle with std::deque 283 15
C++ std::random_shuffle with std::vector 330 14
C++ std::random_shuffle with std::array 299 24
C++ std::search with std::array 325 17
C++ std::search with std::vector 294 15
C++ std::search with std::deque 341 20
C++ std::nth_element with std::deque 508 18
C++ std::nth_element with std::array 338 23
C++ std::nth_element with std::vector 296 19
C++ std::count_if with std::vector 403 16
C++ std::count_if with std::list 290 15
C++ std::count_if with std::deque 307 26
C++ std::count_if with std::multiset 262 17
C++ std::count_if with std::array 325 23
C++ std::count with std::array 381 26
C++ std::count with std::multiset 248 14
C++ std::count with std::deque 335 20
C++ std::count with std::list 269 11
C++ std::count with std::vector 331 23
C++ program to reverse a path in binary search tree using queue 317 17
C++ program to connect nodes at same level 297 21
C++ program to remove all nodes which don%u2019t lie in any path with sum>= k 327 17
C++ program to find ways to color a skewed tree such that parent and child have different colors 321 28
C++ program to find root of the tree where children id sum for every node is given 329 21
C++ program to find largest subtree having identical left and right subtrees 248 14
C++ program to find mirror of a given node in binary tree 325 26
C++ program to find longest path with same values in a binary tree 278 11
C++ program to remove nodes on root to leaf paths of length < k 275 20
C++ program to find a number in minimum steps 279 23
C++ program to find longest consecutive sequence in binary tree 288 11
C++ program to find all duplicate subtrees 281 15
C++ program to find right sibling of a binary tree with parent pointers 331 16
C++ program to find extract leaves of a binary tree in a doubly linked list 236 17
C++ program to check if a given binary tree is sumtree 217 11
C++ program to find simple recursive solution to check whether binary search tree contains dead end 332 19
C++ program to find factor tree of a given number 384 16
C++ program to calculate tilt of binary tree 227 16
C++ program to check if all leaves are at same level 213 15
C++ program to find distance from root to given node in a binary tree 191 14
C++ program to find maximum width of a binary tree 190 14
C++ program to find deepest right leaf node in a binary tree using recursion 194 17
C++ program to find deepest left leaf node in a binary tree using recursion 153 20
C++ program to calculate size of a tree using recursion 348 11
C++ program to transform a binary search tree to greater sum tree 219 14
C++ program to find sum of nodes at k-th level in a tree represented as string 207 16

Comments