I have three versions of this problem
You are given an undirected graph with $$$n$$$ nodes and $$$m$$$ edges. The graph doesn't contain multi edges or self-loops. You will select every edge and randomly give a direction to it. What is the probability of creating a cycle?
Constraints: $$$1 \leq n \leq 100,$$$ $$$1 \leq m \leq \frac{n * (n - 1)}{2}$$$
You are given a graph with n nodes. The graph doesn't have any edge initially. You will select a random pair $$$(u, v), \; u \neq v$$$ and add a directed edge from $$$u$$$ to $$$v$$$. You will do it $$$k$$$ times. You may select the same edge multiple times. What is the probability of creating a cycle?
Constraints: $$$ 1 \leq n, \;k \leq 100$$$
You are given a graph with n nodes. The graph doesn't have any edge initially. You will select a random pair $$$(u, v), \; u \neq v$$$ and add a directed edge from $$$u$$$ to $$$v$$$. You will do it $$$k$$$ times. You can not select the same edge multiple times. What is the probability of creating a cycle?
Constraints: $$$ 1 \leq n, \;k \leq 100$$$
I think the 3rd version can be solved like this: We will count number of DAGs with $$$n$$$ vertices and $$$k$$$ edges. We will consider the lexicographically minimum topological sort(LMTS) of our DAG. Consider a permutation $$$a_1,...,a_n$$$. This permutation is every $$$D$$$'s LMTS if $$$D$$$'s edges are from $$$a_i$$$ to $$$a_j$$$ and $$$i<j$$$ and also there is an edge in $$$D$$$ between every $$$a_i > a_{i+1}$$$.
So using these lemmas we can do $$$dp_{i,j,k}$$$ as number of permutations of $$$i$$$ numbers such that the first element is $$$j$$$ and number of $$$a_x > a_{x+1}$$$ is $$$k$$$. Using these we can easily get the answer.
Your criteria on topological sort being minimal is wrong, for example you say that for 312 being minimal only need 3->1 edge, which is wrong
Suggesting a version 1 solution. Let's solve the problem for a connected graph. If it's unconnected, we can solve the problem for all of its components independantly and then just output the union of the probability for all of them via a simple formula p(a or b) = p(a) + p(b) — p(a and b).
Since our inital graph is connected and the resulting graph needs to be a DAG, it's gonna have a root. I call a root of such a DAG a node, which doesn't have any edges going in it. We can simply brute the root and orient all the edges from it, no two such orientations will intersect, which makes the implementation even easier. Complexity: O(nm).
Que?
The first version can be solved in $$$O(2^n \cdot poly(n))$$$. The answer is $$$\frac{chromatic\ polynomial(-1)}{2^m}$$$.
Or $$$1 - above$$$, probably this is better.
1193A - Amusement Park
Thanks.
The second and the third version might be solved by DP which would count DAGs. I think that we might group the vertices by (for example) the length of the longest path which ends in them and scan them by groups. So, let $$$DP[n][m][k]$$$ be the number of graphs with $$$n$$$ vertices, $$$m$$$ edges such that exactly $$$k$$$ of them have at least one longest path (longest in the whole graph) ending in them. To make a transition, we can connect each new vertex with any subset of old $$$n-k$$$ vertices and we need to connect it with any non-empty subset of old $$$k$$$ vertices. Hard to say if we can reduce the complexity to make it work for $$$n$$$ up to $$$100$$$.