how are we supposed to solve this problem?

https://www.codechef.com/AMR16MOS/problems/AMR16J

I was trying to solve this problem based on strongly connected components — Problem

Strongly connected components can be found using Tarjan's but I haven't studied it yet!

I tried to solve it using the following information —

• All the nodes involved in a cycle are strongly connected.
• Two cycles with atleast one node in common forms strongly connected component.

I marked all the nodes in a cycle with a 'type'. When I encounter a node with some other 'type' (which means it belongs to other cycle as well), I make the disjoint set union of the two cycles.

Is there something I'm missing in my approach?

Here's my code -CODE

I've been trying this problem on spoj but not been able to come up with a optimal solution. The statement translates to — find number of ways to divide a number 'm' into 'n' distinct positive numbers.

1<=m,n<=10^6 also, m*n<=10^6

I was thinking of applying dp, but was stuck at it because it required all the numbers to be distinct. It is obvious that for all values of 'n' around 1400 and above, answer is 0.But that didn't help me in my approach.

Can dp be applied? Or could it be solved using other method?

EDIT: Solved using dp — consider a list of numbers — 1,2,3,....n (minimum possible) and at each index i,increment all numbers (i to n) by some constant.Apply dp here. I still faced some time complexity issues — http://ideone.com/yXCYeo I had to optimise it using sieve — http://ideone.com/jpHIlR

Please let me know if you used some other method.