### Abridged statement↵
There are $N$ vertices in the graph where $N=2^n$ where $n$ is an integer. An array $A$ of size $M$ is given. An edge can be drawn from $i$ to $i\oplus x$ ($\oplus$ represents xor operation) if $x\notin A$. Print $N - 1$ edges such that the edges form a tree.↵
↵
[Statement](https://atcoder.jp/contests/zone2021/tasks/zone2021_f)↵
#### Issue↵
The intended solution uses xor basis / gaussian elimination. However, I found some submissions that uses completely different algorithms that ACs all the testcases. ↵
↵
In summary, the code iterates through all the $x\notin A$, and for each $x$, iterate through all the vertices $v$ from $0$ to $n - 1$. While $v$ and $v \oplus x$ are not connected, connect them and move on to vertex $v + 1$, otherwise, break. This algorithm runs in $O(n)$ as it will only connect edges $n - 1$ times and when it cannot connect edges, it breaks immediately. However, does anyone have a proof that it is correct? Will there be any case where breaking early results in the wrong answer? I tried creating a few test cases by hand and it seems to always generate the correct answer.↵
↵
<spoiler summary="Code">↵
~~~~~↵
REP(x,n){↵
if(!inA[x]){↵
REP(v,n){↵
int a=v,b=(v^x);↵
if(find(a)!=find(b)){↵
edges.pb({a,b});↵
merge(a,b);↵
}↵
else{↵
break;↵
}↵
}↵
}↵
}↵
~~~~~↵
[Submission](https://atcoder.jp/contests/zone2021/submissions/22214634)↵
</spoiler>↵
↵
In another submission, a similar idea was used, however, instead of breaking early, it iterated through all the vertices from $0$ to $n - 1$ as long as $0$ and $x$ are not connected. This clearly results in the correct answer as by looping through all the vertices from $0$ to $n - 1$, it will definitely result in at least one edge being created, so $n - 1$ edges will be created after all iterations. However, it looks as if the algorithm runs in $O(n^2)$. Why does it not TLE?↵
↵
<spoiler summary="Code">↵
~~~~~↵
for(int x=1;x<n;x++){↵
if(!inA[x]) continue;↵
if(uf.same(0,x)) continue;↵
for(int v=0;v<n;v++) add_edge(v,v^x);↵
}↵
~~~~~↵
[Submission](https://atcoder.jp/contests/zone2021/submissions/22207964)↵
</spoiler>↵
↵
There are $N$ vertices in the graph where $N=2^n$ where $n$ is an integer. An array $A$ of size $M$ is given. An edge can be drawn from $i$ to $i\oplus x$ ($\oplus$ represents xor operation) if $x\notin A$. Print $N - 1$ edges such that the edges form a tree.↵
↵
[Statement](https://atcoder.jp/contests/zone2021/tasks/zone2021_f)↵
#### Issue↵
The intended solution uses xor basis / gaussian elimination. However, I found some submissions that uses completely different algorithms that ACs all the testcases. ↵
↵
In summary, the code iterates through all the $x\notin A$, and for each $x$, iterate through all the vertices $v$ from $0$ to $n - 1$. While $v$ and $v \oplus x$ are not connected, connect them and move on to vertex $v + 1$, otherwise, break. This algorithm runs in $O(n)$ as it will only connect edges $n - 1$ times and when it cannot connect edges, it breaks immediately. However, does anyone have a proof that it is correct? Will there be any case where breaking early results in the wrong answer? I tried creating a few test cases by hand and it seems to always generate the correct answer.↵
↵
<spoiler summary="Code">↵
~~~~~↵
REP(x,n){↵
if(!inA[x]){↵
REP(v,n){↵
int a=v,b=(v^x);↵
if(find(a)!=find(b)){↵
edges.pb({a,b});↵
merge(a,b);↵
}↵
else{↵
break;↵
}↵
}↵
}↵
}↵
~~~~~↵
[Submission](https://atcoder.jp/contests/zone2021/submissions/22214634)↵
</spoiler>↵
↵
In another submission, a similar idea was used, however, instead of breaking early, it iterated through all the vertices from $0$ to $n - 1$ as long as $0$ and $x$ are not connected. This clearly results in the correct answer as by looping through all the vertices from $0$ to $n - 1$, it will definitely result in at least one edge being created, so $n - 1$ edges will be created after all iterations. However, it looks as if the algorithm runs in $O(n^2)$. Why does it not TLE?↵
↵
<spoiler summary="Code">↵
~~~~~↵
for(int x=1;x<n;x++){↵
if(!inA[x]) continue;↵
if(uf.same(0,x)) continue;↵
for(int v=0;v<n;v++) add_edge(v,v^x);↵
}↵
~~~~~↵
[Submission](https://atcoder.jp/contests/zone2021/submissions/22207964)↵
</spoiler>↵
↵
