OJ Board

Any hints for this one? It reduces to counting the number of lattice points in a triangle in 3-D space. How do you do that? Is there a generalisation of Pick's theorem which could be applied here?

I finally managed to get my solution accepted. However, the accepted solution gives an output of 1 on the following input:

1
7 8
0 1
1 0
2 3
3 2
1 4
3 5
4 6
5 6

The correct answer should be 2, shouldn't it?

@Yang, could you please tell me the output of your code on this case.

Would the answer for the case P=1, L=0 be 0 or 1?

I am sorry. I misread your post.

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 don't understand that. If a vertex belongs to a cycle, then, its in-degree>=1 and out-degree>=1. Hence, if a vertex has zero in-degree ...

That would be true if I was considering the DAG formed by the strongly connected components. That is not the DAG in picture. In this DAG, the only vertices that remain are those which did not belong to any cycle in the original graph. There is an edge from u to v, where u and v are two vertices in ...

I am deleting all the vertices which belong to a cycle. I am doing this on the transitive closure so that the connectivity of the other vertices is not affected.

The intention of my algorithm is not to make the graph strongly connected. I will try to clarify what I meant.

1) We might as well consider the graph G'(after making it a DAG, as described in my previous post). Is this correct?
2) Assuming that it is correct, we need to add atleast max(c1, c2 ...

You only need to report the answer modulo 100000007. So the product of primes being O(n!) does not matter.

Hint : Euler's totient function

If I understand the problem correctly, it is asking us to find the minimum number of edges to add, so that, in the resulting graph, every vertex belongs to a cycle. I am getting WA for the following algorithm. Could someone please provide a counter?

Let G be the given graph.
1) G' = transitive ...

Any hints on this one? One reduction is to maximum matching, which can be done with Edmonds' blossom algorithm. Is there anything simpler?