diff options
| author | f1or1an <110727007+f1or1an@users.noreply.github.com> | 2023-11-15 03:44:56 +0100 |
|---|---|---|
| committer | mzuenni <mzuenni@users.noreply.github.com> | 2023-11-15 11:48:17 +0100 |
| commit | a7f4c162112a1f80b823984baa0c737df9a7f5e0 (patch) | |
| tree | 5ef719272c03f6628e1de1376ea6828fa111c8d7 /graph | |
| parent | 874a5628f813c70522a0998c2e3eacbae60d7577 (diff) | |
hld: fix bug
Nach Initialisierung mit root!=0 war nxt[root]!=root.
Dadurch gab es (mindestens, aber nicht nur) diesen Fehler:
Beim Aufruf von for_intervals mit u=v=root wurde f mit
max(in[root], in[nxt[root]]
=max(0, in[0])
=in[0],
einer quasi beliebigen Zahl, aufgerufen
Diffstat (limited to 'graph')
| -rw-r--r-- | graph/hld.cpp | 2 |
1 files changed, 1 insertions, 1 deletions
diff --git a/graph/hld.cpp b/graph/hld.cpp index fae6030..65d3f5c 100644 --- a/graph/hld.cpp +++ b/graph/hld.cpp @@ -22,7 +22,7 @@ void dfs_hld(int v = 0, int from = -1) { void init(int root = 0) { int n = sz(adj); - sz.assign(n, 1), nxt.assign(n, 0), par.assign(n, -1); + sz.assign(n, 1), nxt.assign(n, root), par.assign(n, -1); in.resize(n), out.resize(n); counter = 0; dfs_sz(root); |