PROBLEM LINK:Author: Aman Kumar Gupta Tester: D Teja Vardhan Reddy Editorialist: Aman Kumar Gupta DIFFICULTY:EASYMEDIUM PREREQUISITES:Graph theory, Combinatorics PROBLEM:A short and concise description of the problem statement. QUICK EXPLANATION: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 fromandto each other using the same colour, and the ones not reachable in both ways, with different colours. EXPLANATION:Basically, it's clear from the problem itself that the nodes which are reachable fromandto 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 AND TESTER'S SOLUTIONS:Author's solution can be found here. Tester's solution can be found here.
This question is marked "community wiki".
asked 07 Feb, 00:01
