Graph theory, Combinatorics
A short and concise description of the problem statement.
Given a graph with N nodes and M - 1 edges. You have also been given K colours and you are required to find the number of ways to colour the nodes which can be reached from-and-to each other using the same colour, and the ones not reachable in both ways, with different colours.
Basically, it’s clear from the problem itself that the nodes which are reachable from-and-to each other form strongly connected components.
So, we just need to find the number of strongly connected components. Let this count be ‘s’. Then if K is less than ‘s’, answer is -1. Else the answer is k! / (k - s)!.
Author’s solution can be found here.
Tester’s solution can be found here.