OJ Board

I'll talk about my method here. Hope it would be of help.

-- spoiler --
/* those who wish to solve the problem themselves might not want to read ahead */

First we can limit our choice of link to only some nodes - Only those that are leaves/roots had to be considered.
This should be fairly easy to ...

Yes, it should be 2.
and the output of my program is 2 for the testcase above.

I think maybe you forget to search on the root? dunno..

oh, and the answer to the question..
A more general question, for P=2 and L=2, and if we have edge (0,0) and (0,1). Is the solution 0, since you can never leave ...

No......
I do understand your algorithm.

Sorry if I was too implicit.
What I meant is that for those nodes in the cycles, they don't necessary need additional links even if they are roots/leaves.
I already tried to emphasize that point and I think you should try reading the constraints more ...

Mind that while you contract your graph into an DAG, you contracted the cycles into single vertices.
and if the contracted vertices happen to be the leaf/root of your DAG, you might requre less edges added than max(c1, c2).
(since the nodes in the cycle are actually already linked to itselfs)

The algorithm you described is not exactly right for this problem.

In this problem the requirement is:
"every node can click one or more links and then return to itself"
so there are actually two requirements:
1) by clicking one or more links
2) return to the node itself

And the intention of your ...

649 You who?

I was trying to understand this problem but seemed to have some difficulties.

My understanding of the problem is as below:
Given a graph G, divide its vertices into two groups such that
1) the number of vertices in two group differ by at most 1
2) the maximum number of not-acquainted ...