I used Tarjan Algo, based on DFS and union-find sets, but got Crash AV #3. I made a extreme data myself, like a chain from Node #0. And it really crashed with DEV-C++. I tried to enlarge the size of stack, but it seemed workless. After debugging for so long, I still can't explain why it got stuck at Node #49xxx (The program works on every "smaller data"). Do I have to make a "stack" myself? No, I came up with an idea--randomize. And with that I ACed with no difficulty.
Here is the thing, maybe you picked Node #0 as the root of the tree, but why not change to a random one? I think data #3 is such a data that will make the first algo crash.
Sorry for my poor English, btw.

I had the same problems with this problem but increasing size of the stack helped me. Post here your e-mail and i'll send you my code. I think you understand my code because i made it the same way with you(dfs+disjoint set)

tiancaihbATsinaDOTcom

No, forget about it. I must have writen a wrong code
The right one is #pragma comment(linker, "/STACK:16777216").
Well, that's embarrassing because you won't get CE even if it's wrong.
I wrote before: #pragma comment(linker, "/STACK:64777216")

Edited by author 16.01.2010 12:54

Edited by author 16.01.2010 12:55