# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
NORZ
Just gonna pretend that i understand this stuff
What are you doing on this website
I'm sori, I'm just a nerd trying to learn how to be funny from the best.
Touchwood
When this type of formulation work? is this for this particular question or if you have some more problem Please Share. Thanks for explaining
190E - Counter Attack
653E - Bear and Forgotten Tree 2
1242B - 0-1 MST
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 theprev
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
andnext
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 theprev
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)
Thanks for the implementation! As a consequence, we can find the DFS tree of the complement graph in linear time, which means we can find 2-vertex-connected and 2-edge-connected components (and hence, the block-cut tree and the bridge tree respectively) of an arbitrary undirected graph in the same time complexity.
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.
This algorithm is indeed really cool. I remember reading about it in this comment at some point but seemed to have forgotten it over time, so thanks for the reminder!
What does $$$V$$$ and $$$N$$$ mean in $$$V∩N(u_1)∩⋯∩N(u_i)⊆N(u_i)$$$?
$$$V$$$ is the set of all vertices of the graph, and $$$N(u)$$$ denotes the set of neighbours of a vertex $$$u$$$.
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 ?
You can get a better bound here. Note that whenever you skip a vertex $$$v$$$ while in the DFS for vertex $$$u$$$, it is because $$$(u, v)$$$ is not an edge in the complement graph. This is the same as saying that $$$(u, v)$$$ is an edge in the input graph. So the total number of skips can be at most double the number of edges in the input graph, which is $$$m$$$.
The graph I mentioned in the edit should have O(n * n) skips, right? Also m is of the order O(n * n) in that test case so we can say there are O(m) skips. But since m is bounded by min(n * (n + 1) / 2, 200000)), we won't be getting such test case for large value of n.
Am i right or missing something ?
Yes, it will take $$$O(m)$$$ skips regardless of what your graph is. In this case, $$$m = O(n^2)$$$, so it does not contradict what you said.
Thanks!