NORZ

Just gonna pretend that i understand this stuff

When this type of formulation work? is this for this particular question or if you have some more problem Please Share. Thanks for explaining

I just realized that there is also beautiful a linear-time solution to DFS, working in provable $$$O(n + m)$$$ time, using doubly-linked lists and an idea similar to "dancing links".

The main idea is to store the "global visited list" as a doubly linked list. After you call dfs(child), you get back to the next value by going through the prev pointers in the linked list.

It is important that the "deletion" from the linked list does not re-link the deleted node (let it point to the old prev and next nodes). You can prove intuitively that the "invalid" list you are traversing from this deleted node is at any time a superset of the real "valid" list. Also, because we use the prev pointers to go from an invalid (visited) node to a valid (unvisited) node, then these operations amortize beautifully (just like the principle of a stack).

Implementation: 219699489 (I tried to make it as similar as possible to the original DSU implementation for ease of comparison)

One of my favorite implementation of the "complement traversal" problem is as follows.

The problem becomes trivial if $$$n \leq \sqrt{m}$$$ because the simple $$$O(n^2)$$$ algorithm wins. Otherwise suppose that $$$0$$$ is the vertex with the minimum degree among the graph $$$G$$$. Hence $$$\mathrm{deg}(0) \leq \frac{2m}{n} = O(\sqrt{m})$$$. Let $$$X = V \setminus \{0\} \setminus N(0)$$$. i.e., those vertices which are not adjacent to the vertex $$$0$$$ in $$$G$$$. $$$X \cup \{0\}$$$ should be connected in $$$\bar{G}$$$. Brute force on $$$N_0$$$ gives an $$$O((\frac{2m}{n})^2) = O(m)$$$ algo.

What does $$$V$$$ and $$$N$$$ mean in $$$V∩N(u_1)∩⋯∩N(u_i)⊆N(u_i)$$$?

In the naive DFS solution, won't there be O(n) skips per vertex which in worst case might lead to O(n * n) skips ?

In the following graph
1: 2 3 4 5 ..... n-1
.
.
.
n-2: 2 3 4 ... n-4
n-1: 2 3 4 .... n-3
n: 2 3 4 5 .... n-2

When starting dfs from 1, we will skip all the vertices from 2 to n-1 and make a recursive call to dfs(n). dfs(n) will skip all the vertices from 2 to n — 2 again and will make a recursive call to dfs(n-1) and so on. This way, won't we make a total of O(n * n) skips ?