Making It Bipartite
Contest: Codeforces Round 768 (Div. 1)
Difficulty rating: 3400
Tags: flows, graph matchings, graphs, number theory

You are given an undirected graph of $$$n$$$ vertices indexed from $$$1$$$ to $$$n$$$, where vertex $$$i$$$ has a value $$$a_i$$$ assigned to it and all values $$$a_i$$$ are different. There is an edge between two vertices $$$u$$$ and $$$v$$$ if either $$$a_u$$$ divides $$$a_v$$$ or $$$a_v$$$ divides $$$a_u$$$.

Find the minimum number of vertices to remove such that the remaining graph is bipartite, when you remove a vertex you remove all the edges incident to it.

Input format:
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5\cdot10^4$$$) — the number of vertices in the graph.

The second line of each test case contains $$$n$$$ integers, the $$$i$$$-th of them is the value $$$a_i$$$ ($$$1 \le a_i \le 5\cdot10^4$$$) assigned to the $$$i$$$-th vertex, all values $$$a_i$$$ are different.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5\cdot10^4$$$.

Output format:
For each test case print a single integer — the minimum number of vertices to remove such that the remaining graph is bipartite.

Constraints:
Time limit: 4.0 s
Memory limit: 512.0 MB

Note:
In the first test case if we remove the vertices with values $$$1$$$ and $$$2$$$ we will obtain a bipartite graph, so the answer is $$$2$$$, it is impossible to remove less than $$$2$$$ vertices and still obtain a bipartite graph.

BeforeAfter test case #1

In the second test case we do not have to remove any vertex because the graph is already bipartite, so the answer is $$$0$$$.

BeforeAfter test case #2

In the third test case we only have to remove the vertex with value $$$12$$$, so the answer is $$$1$$$.

BeforeAfter test case #3

In the fourth test case we remove the vertices with values $$$2$$$ and $$$195$$$, so the answer is $$$2$$$.

BeforeAfter test case #4

Example input:
4
4
8 4 2 1
4
30 2 3 5
5
12 4 6 2 3
10
85 195 5 39 3 13 266 154 14 2

Example output:
2
0
1
2

Editorial:
First of all, let's analyze what happens when there are $$$3$$$ vertices $$$x$$$, $$$y$$$ and $$$z$$$ such that $$$a_x|a_y$$$, $$$a_x|a_z$$$ and $$$a_y|a_z$$$, if this happens then the graph cannot be bipartite because there would be a cycle of size $$$3$$$, therefore there cannot be such a triple ($$$x$$$, $$$y$$$, $$$z$$$), this condition, besides to being necessary, is sufficient since we can separate the graph into two sets, set $$$A$$$: vertices that have edges towards multiples, set $$$B$$$: vertices that have edges towards divisors, keep in mind that a vertex cannot exist in two sets at the same time if the condition is fulfilled, now note that there are no edges between elements of the same set because if this happens it would mean that they belong to different sets and it would be a contradiction, then the problem is to find the minimum number of vertices to remove such that in the remaining vertices there is no such triple of numbers ($$$x$$$, $$$y$$$, $$$z$$$). Now instead of minimizing the number of vertices to remove, let's try to maximize the number of vertices that will remain in the graph.
Let us define the directed graph $$$G$$$ as the graph formed by $$$n$$$ vertices, and directed edges ($$$u$$$, $$$v$$$) such that $$$a_v|a_u$$$, now the problem is reduced to finding the maximum number of vertices such that in the graph formed among them, no vertex has ingoing edges and outgoing edges at the same time, formally for each vertex $$$x$$$ the following property must be kept $$$indegree_x = 0$$$ or $$$outdegree_x = 0$$$, in this way we guarantee that there is no triple ($$$x$$$, $$$y$$$, $$$z$$$) such that $$$a_x|a_y$$$, $$$a_x|a_z$$$ and $$$a_y|a_z$$$.
Now let's define the graph $$$G'$$$ as a copy of the graph $$$G$$$. Formally for each directed edge ($$$u$$$, $$$v$$$) in the graph $$$G$$$ there is an directed edge ($$$u'$$$, $$$v'$$$) in the graph $$$G'$$$. On the other hand, let's define the graph $$$H = G + G'$$$ and we will also add new directed edges ($$$u'$$$, $$$u$$$), this graph $$$H$$$ is a $$$DAG$$$, it is easy to see that the edges always go from a vertex $$$u$$$ to a vertex $$$v$$$ only if $$$a_u > a_v$$$, except for the edges ($$$u'$$$, $$$u$$$), which in this case $$$a_{u'} = a_u$$$, these edges are the ones that connect $$$G'$$$ to $$$G$$$, but since they always go in one direction pointing towards $$$G$$$, the property of $$$DAG$$$ is still fulfilled.
Now the only thing we have to do is find the largest antichain in the graph $$$H$$$, this can be done using the Dilworth's Theorem, modeling the problem as a bipartite matching, we can use some flow algorithm such as Dinic's Algorithm, or Hopcroft Karp's Algorithm, which is specific to find the maximum bipartite matching.
Proof:
First of all we realize that the graph $$$G$$$ is a special graph since if there is an indirect path from a vertex $$$u$$$ to a vertex $$$v$$$ then there is always a direct edge between them, this is true because if we have $$$3$$$ vertices $$$x$$$, $$$y$$$ and $$$z$$$ such that $$$a_x|a_y$$$ and $$$a_y|a_z$$$ then always $$$a_x|a_z$$$. With this we can say that two elements are not reachable with each other if and only if there are no edges between them. Now let's say that all the vertices in the graph $$$G$$$ are white and all the vertices in the graph $$$G'$$$ are black, let us denote $$$f(x)$$$ a function such that $$$f(u') = u$$$, where the vertex $$$u$$$ from the graph $$$G$$$ is the projection of the vertex $$$u'$$$ from the graph $$$G'$$$. Now let's divide the proof into two parts.
*First part:
Lemma 1: Every antichain of $$$H$$$ can be transformed into a valid set of vertices such that they form a bipartite graph.
Proof Lemma 1: Let's divide the antichain of $$$H$$$ into two sets, white vertices and black vertices, Let us define the set of white vertices as $$$W$$$ and the set of all black vertices as $$$B$$$, now we will create a set $$$S$$$ = {$$$f(x)$$$ | $$$x \in B$$$}. It is easy to see that no element in $$$S$$$ belongs to $$$W$$$ since if this happens it would mean that there is an element $$$x$$$ such that $$$x$$$ belongs to $$$B$$$ and $$$f(x)$$$ belongs to $$$W$$$ and by the concept of antichain that would not be possible. It is also easy to see that the elements of the set $$$S$$$ are an antichain since the set $$$S$$$ is a projection of vertices from the set $$$B$$$ of the graph $$$G'$$$ on $$$G$$$. Now we have that there are no edges between the vertices of the set $$$S$$$ and there are no edges between the vertices of the set $$$W$$$, with this it is proved that the graph is bipartite.
*Second part:
Lemma 2: Every valid set of vertices such that they form a bipartite graph can be transformed into an antichain of $$$H$$$.
Proof Lemma 2: Let us denote $$$f^{-1}(x)$$$ a function such that $$$f^{-1}(u) = u'$$$, where vertex $$$u$$$ from graph $$$G$$$ is the projection of vertex $$$u'$$$ from graph $$$G'$$$. Let us denote the set $$$A$$$ as all vertices that have $$$indegree$$$ greater than $$$0$$$ and $$$B$$$ to all vertices that have $$$outdegree$$$ greater than $$$0$$$, now we will create a set $$$C$$$ = {$$$f^{-1}(x)$$$ | $$$x \in A$$$}, It is easy to see that set $$$B$$$ is an antichain since if one vertex has an edge to another vertex then some of them would have $$$indegree$$$ greater than $$$0$$$ and would contradict the definition of set $$$B$$$, we can also see that the elements in set $$$A$$$ are an antichain since all the elements have $$$outdegree = 0$$$ so no vertex point towards any other vertex, with this we can define that all the elements in $$$C$$$ are an antichain since they are a projection of vertices of the set $$$A$$$ from the graph $$$G$$$ on $$$G'$$$, Now we want to proof that the union of set $$$B$$$ and $$$C$$$ is an antichain, this is very simple to see since the vertices of set $$$B$$$ belong to $$$G$$$ and the vertices of $$$C$$$ belong to $$$G'$$$, therefore there is no edge from any vertex in $$$B$$$ to a vertex in $$$C$$$ since there are no edges from $$$G$$$ to $$$G'$$$. Now it only remains to proof that from set $$$C$$$ no vertex of set $$$B$$$ can be reached, this is proved taking into account that the vertices reachable from the set $$$C$$$ in the graph $$$G$$$ are the same that the vertices reachable from the set $$$A$$$ in the graph $$$G$$$, and as no vertex of $$$A$$$ has edges towards $$$B$$$, this cannot happen. Therefore the union of the sets $$$B$$$ and $$$C$$$ is an antichain of $$$H$$$.
Then we can say that the two problems are equivalent and it is shown that finding the maximum antichain we obtain the largest bipartite graph.
The graph $$$G$$$ contains $$$n$$$ vertices and around $$$n\cdot log(n)$$$ edges (since the numbers $$$a_x$$$ are different and the sum of the divisors from $$$1$$$ to $$$n$$$ is around $$$n\cdot log(n)$$$). The graph $$$G'$$$ is a duplicate of $$$G$$$ then we would have $$$n\cdot log(n)\cdot2 + n$$$ edges and $$$2\cdot n$$$ vertices, if we use the Hopcroft Karp algorithm we would obtain a time complexity of $$$O(n\cdot log(n)\cdot sqrt(n))$$$ and a space complexity of $$$O(n\cdot log(n))$$$.