Метод двоичного подъёма - История изменений

Ctrlalt в 18:29, 27 июня 2023

2023-06-27T18:29:54Z

← Предыдущая версия		Версия от 18:29, 27 июня 2023
Строка 18:		Строка 18:
	void dfs(int v, int parent) {		void dfs(int v, int parent) {
	depth[v] = (v == parent ? 0 : depth[parent] + 1);		depth[v] = (v == parent ? 0 : depth[parent] + 1);
	l[v] = ++~~timer~~;		l[v] = timer++;

	ancestor[v][0] = parent;		ancestor[v][0] = parent;
Строка 25:		Строка 25:

	for (int to : graph[v])		for (int to : graph[v])
	if (!~~l[to]~~)		if (to != parent)
	dfs(to, v);		dfs(to, v);

	r[v] = ++~~timer~~;		r[v] = timer++;
	}		}

Ctrlalt: Отмена правки 2694, сделанной Ctrlalt (обсуждение)

2021-07-31T08:23:00Z

Отмена правки 2694, сделанной Ctrlalt (обсуждение)

← Предыдущая версия		Версия от 08:23, 31 июля 2021
Строка 59:		Строка 59:
	}		}
	};		};

			== Ссылки ==
			* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]
			* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Метод двоичного подъёма]
			* [https://algorithmica.org/ru/lca algorithmica.org — Корневые деревья]
			* [https://usaco.guide/gold/tree-euler usaco.guide — Euler Tour Technique]
			* [https://usaco.guide/plat/binary-jump usaco.guide — Binary Jumping]
			* [https://github.com/indy256/codelibrary/blob/master/java/graphs/lca/LcaSparseTable.java indy256/codelibrary/java/graphs/lca/LcaSparseTable.java] (несмотря на название, приведён код метода двоичного подъёма)
			* [http://github.com/ADJA/algos/blob/master/Graphs/LCABinary.cpp ADJA/algos/Graphs/LCABinary.cpp]

			[[Category:Наименьший общий предок]]

Ctrlalt в 08:13, 31 июля 2021

2021-07-31T08:13:13Z

← Предыдущая версия		Версия от 08:13, 31 июля 2021
Строка 1:		Строка 1:
	~~void dfs(int v, int parent)~~ { ~~//если v - корень, то parent == v~~		struct Graph {
	~~tIn[v] = timer++~~;		vector<vector<int>> graph, ancestor;
	~~p[v][0] = parent;~~		vector<int> l, r, depth;
	~~for (~~int ~~i = 1; i < MAX_H; i++)~~		int timer = 0;
	~~p[v][i] = p[p[v][i - 1]][i - 1]~~;
	~~for (~~int i = 0; ~~i < g[v].size(); i++)~~
	~~dfs(g[v][i], v);~~
	~~tOut[v] = timer++;~~
	}

	~~bool isAncestor~~(int a, int b) {		Graph(int vertexCount) :
	~~return tIn[a] <= tIn[b] && tOut[b] <= tOut[a];~~		graph(vertexCount),
	}		ancestor(vertexCount, vector<int>(20)),
			l(vertexCount),
			r(vertexCount),
			depth(vertexCount) {}

	~~int lca~~(int a, int b) {		void addEdge(int a, int b) {
	~~if (isAncestor(a, b))~~		graph[a].push_back(b);
	~~return~~ a;		graph[b].push_back(a);
	~~if (isAncestor~~(b~~, a)~~)
	~~return~~ b;
	~~for (int i = MAX_H - 1; i >= 0; i--) {~~
	~~if (!isAncestor~~(p[a~~][i], b~~))
	~~a = p[a][i]~~;
	}		}
	~~return p~~[a][0];
	}		void dfs(int v, int parent) {
			depth[v] = (v == parent ? 0 : depth[parent] + 1);
	== ~~Ссылки ==~~		l[v] = ++timer;
	* [~~http://e~~-~~maxx.ru/algo/lca_simpler e~~-~~maxx.ru &mdash~~; ~~Наименьший общий предок. Нахождение за O~~(~~log N~~) (~~метод двоичного подъёма~~)]
	* [~~http://neerc.ifmo.ru/wiki/index.php?title~~=~~%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki~~ &~~mdash~~; ~~Метод двоичного подъёма]~~		ancestor[v][0] = parent;
	* [http://github.com/indy256/codelibrary/blob/master/java/src/LcaSparseTable.java CodeLibrary — ~~LCA: Sparse Table]~~ (~~несмотря на название~~, ~~приведён код метода двоичного подъёма~~)		for (int i = 1; i < ancestor[v].size(); i++)
	* [~~http://github~~.~~com/ADJA/algos/blob/master/Graphs/LCABinary.cpp Algos &mdash~~; ~~Finding LCA~~ (~~Least common~~ ancestor) ~~of two vertices in the tree~~]		ancestor[v][i] = ancestor[ancestor[v][i - 1]][i - 1];

	[[~~Category:Наименьший общий предок~~]]		for (int to : graph[v])
			if (!l[to])
			dfs(to, v);

			r[v] = ++timer;
			}

			void prepare(int root) {
			dfs(root, root);
			}

			bool isAncestor(int a, int b) {
			return l[a] <= l[b] && r[b] <= r[a];
			}

			int lca(int a, int b) {
			if (isAncestor(a, b))
			return a;
			if (isAncestor(b, a))
			return b;

			for (int i = ancestor[a].size() - 1; i >= 0; i--)
			if (!isAncestor(ancestor[a][i], b))
			a = ancestor[a][i];

			return ancestor[a][0];
			}

			int distance(int a, int b) {
			int l = lca(a, b);
			int da = depth[a] - depth[l];
			int db = depth[b] - depth[l];
			return da + db;
			}
			};

Ctrlalt в 20:41, 1 октября 2014

2014-10-01T20:41:04Z

← Предыдущая версия		Версия от 20:41, 1 октября 2014
Строка 1:		Строка 1:
			void dfs(int v, int parent) { //если v - корень, то parent == v
			tIn[v] = timer++;
			p[v][0] = parent;
			for (int i = 1; i < MAX_H; i++)
			p[v][i] = p[p[v][i - 1]][i - 1];
			for (int i = 0; i < g[v].size(); i++)
			dfs(g[v][i], v);
			tOut[v] = timer++;
			}

			bool isAncestor(int a, int b) {
			return tIn[a] <= tIn[b] && tOut[b] <= tOut[a];
			}

			int lca(int a, int b) {
			if (isAncestor(a, b))
			return a;
			if (isAncestor(b, a))
			return b;
			for (int i = MAX_H - 1; i >= 0; i--) {
			if (!isAncestor(p[a][i], b))
			a = p[a][i];
			}
			return p[a][0];
			}

	== Ссылки ==		== Ссылки ==
	* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]		* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]

Ctrlalt в 14:42, 23 августа 2014

2014-08-23T14:42:54Z

← Предыдущая версия		Версия от 14:42, 23 августа 2014
Строка 2:		Строка 2:
	* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]		* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Метод двоичного подъёма]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Метод двоичного подъёма]
			* [http://github.com/indy256/codelibrary/blob/master/java/src/LcaSparseTable.java CodeLibrary — LCA: Sparse Table] (несмотря на название, приведён код метода двоичного подъёма)
	* [http://github.com/ADJA/algos/blob/master/Graphs/LCABinary.cpp Algos — Finding LCA (Least common ancestor) of two vertices in the tree]		* [http://github.com/ADJA/algos/blob/master/Graphs/LCABinary.cpp Algos — Finding LCA (Least common ancestor) of two vertices in the tree]

	[[Category:Наименьший общий предок]]		[[Category:Наименьший общий предок]]

Ctrlalt: Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (мет…»

2014-08-23T12:28:10Z

Новая страница: «== Ссылки == * [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (мет…»

Новая страница

== Ссылки ==
* [http://e-maxx.ru/algo/lca_simpler e-maxx.ru — Наименьший общий предок. Нахождение за O(log N) (метод двоичного подъёма)]
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%BF%D0%BE%D0%B4%D1%8A%D0%B5%D0%BC%D0%B0 neerc.ifmo.ru/wiki — Метод двоичного подъёма]
* [http://github.com/ADJA/algos/blob/master/Graphs/LCABinary.cpp Algos — Finding LCA (Least common ancestor) of two vertices in the tree]

[[Category:Наименьший общий предок]]