694600A - Despite everything, its still MEX
What is the maximum possible $$$MEX$$$? find an upper bound for the final $$$MEX$$$.
Since size of $$$c$$$ is $$$n$$$. The $$$MEX$$$ of $$$c$$$ can be at most $$$n$$$ (why?). Hence each index $$$i$$$ $$$(1 \le i \le n)$$$, can be categorized into one of three categories:
($$$a_i \ge n$$$ and $$$b_i \ge n$$$): such indices can be ignored as the choice here doesn't matter, neither will contribute to the $$$MEX$$$
($$$a_i \ge n$$$ and $$$b_i \lt n$$$) or ($$$b_i \ge n$$$ and $$$a_i \lt n$$$): when exactly one of $$$a_i$$$ and $$$b_i$$$ is less than $$$n$$$, the choice is obvious, set $$$c_i$$$ to the element less than $$$n$$$
($$$a_i \lt n$$$ and $$$b_i \lt n$$$): this is the non-trivial case. Try working out the example test cases manually. What do you observe?
Work through the following example:
Its quite trivial to see that for $$$c = [0, 1, 2, 3]$$$, the $$$MEX = 4$$$ is maximum possible $$$MEX$$$. One way to deconstruct this answer is to create a graph with $$$n$$$ nodes labelled $$$0, 1, ... 4$$$. Now for each index $$$i$$$ ($$$1 \le i \le n$$$), create an edge between nodes labelled $$$a_i$$$ and $$$b_i$$$. In this case the final graph would look like this:
In this case the resulting graph is a tree. From this graph we can choose all but one node to include in the array $$$c$$$, its trivial to see that the optimal element to exclude would be the maximum number which in this case is $$$4$$$. Try generalizing this logic for a tree with any $$$n$$$ nodes. What about a graph of $$$n$$$ nodes that isn't a tree?
Consider the following example:
On creating a graph in the same manner we get:
since the graph has a "loop", this isn't a tree anymore and we can include all elements of the graph in $$$c$$$. Hence the maximum $$$MEX$$$ will be $$$4$$$. One possible construction is $$$c = [1, 2, 3, 0]$$$.
We'll only be working with the non-trivial indices as discussed in Hint 2. Set up a graph initially with $$$n$$$ nodes labelled $$$0,1,...n-1$$$. For each index $$$i$$$ ($$$1 \le i \le n$$$) that is non-trivial, create an edge between nodes $$$a_i$$$ and $$$b_i$$$. We'll end up with several disjoint graph components, some that are trees and some that aren't. For each node we'll keep track of the following properties:
an index $$$root$$$ keeping track of the root node of the disjoint graph it's present in.
an integer $$$M$$$ keeping track of the maximum value present in it's disjoint graph.
a boolean $$$looped$$$ that is set to $$$true$$$ when a "loop" is present in it's disjoint group, $$$false$$$ otherwise.
Keep in mind that edges can start and end at the same node to create a "loop" of one element. this can happen when $$$a_i = b_i \lt n$$$.
Initially (before creating the edges), for each index $$$i$$$ ($$$1 \le i \le n$$$) set:
$$$root_i = i$$$ since there are no edges, there are $$$n$$$ disjoint graphs initially each with one node, which itself is the root node.
$$$M_i = i$$$ since only one element is present in each disjoint graph, it itself is the maximum value.
$$$looped_i = false$$$ since there are no edges, it is a tree with one node.
When creating an edge, we'll either be combining two disjoint graphs into one, or create a "loop" inside a disjoint graph if it isn't already present. To update the edges, we'll iterate through all non-trivial indices $$$i$$$ ($$$1 \le i \le n$$$). For each index $$$i$$$ we'll perform the following operations in order:
set $$$root_{a_i} = root_{b_i}$$$. When we keep doing this, for any node $$$j$$$ which is a root node, we have $$$root_j = j$$$.
It will be redundant to update the value of $$$M$$$ and $$$looped$$$ for all the nodes in the graph as it would be lead of a time complexity of $$$\mathcal{O}(n^2)$$$. Instead we'll just update the value of $$$M_{root_{b_i}}$$$ and $$$looped_{root_{b_i}}$$$, and when we require $$$M_j$$$ for any index $$$j$$$, we'll just find $$$root_j$$$, and update $$$M_j$$$ = $$$M_{root_j}$$$. We can do the same for $$$looped_j$$$. This would lead to a time complexity of $$$\mathcal{O}(n\cdot\alpha (n))$$$
set $$$M_{root_{b_i}} = max(M_{root_{b_i}}, M_{root_{a_i}})$$$
set $$$looped_{root_{b_i}} = (looped_{root_{b_i}} \ | \ looped_{root_{a_i}} \ | \ (root_{a_i} == root_{b_i}))$$$
After creating all edges, we'll have several disjoint graphs. We'll iterate from $$$i = 0$$$ to $$$i = n$$$, to check the first element $$$j$$$ that cannot be included in $$$c$$$ after optimally choosing elements from each disjoint graph. This will be our final answer. For each index $$$i$$$, either one of the following two conditions must hold if it can be included in $$$c$$$. This can be done in $$$\mathcal{O}(n)$$$
$$$M_i \neq i$$$
$$$looped_i = true$$$
The time complexity of our solution is $$$\mathcal{O}(n\cdot\alpha (n))$$$ where $$$\alpha$$$ is the inverse ackermann function and for all practical purposes $$$\alpha (n) \le 4$$$, which reduces our final time complexity to $$$\mathcal{O}(n)$$$ .
A bug free implementation of the above logic is given below
#include<bits/stdc++.h>
#include<vector>
using namespace std;
struct DSU{
vector<int> parent;
vector<int> M;
vector<bool> looped;
DSU(int n){
parent.resize(n);
M.resize(n);
looped.assign(n, false);
for(int i = 0; i < n; i++){
parent[i] = i;
M[i] = i;
}
}
int find(int i){
if(parent[i] == i){return i;}
parent[i] = find(parent[i]);
return parent[i];
}
void merge(int i, int j){
int ri = find(i);
int rj = find(j);
if(ri == rj){looped[rj] = true;}
else{
parent[ri] = rj;
M[rj] = max(M[rj], M[ri]);
looped[rj] = looped[rj] | looped[ri];
}
}
};
void solve()
{
int n; cin >> n;
vector<int> a(n); for(int i = 0; i < n; i++){cin >> a[i];}
vector<int> b(n); for(int i = 0; i < n; i++){cin >> b[i];}
DSU dsu(n);
for(int i = 0; i < n; i++){
if(a[i] >= n && b[i] >= n){continue;}
else if(a[i] >= n){dsu.merge(b[i], b[i]);}
else if(b[i] >= n){dsu.merge(a[i], a[i]);}
else{dsu.merge(a[i], b[i]);}
}
int mex = 0;
for(; mex < n; mex++){
int parent = dsu.find(mex);
if(dsu.M[parent] > mex){continue;}
else{
if(dsu.looped[parent]){continue;}
else{break;}
}
}
cout << mex << "\n";
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
//int t = 1;
int t; cin >> t;
for(int i = 0; i < t; i++) {solve();}
return 0;
}
