Циклы в графе. Двудольность - История изменений

Ctrlalt в 15:15, 24 мая 2023

2023-05-24T15:15:25Z

← Предыдущая версия		Версия от 15:15, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==
			<youtube width="300" height="180">pB83tSvoBuc</youtube>
			<youtube width="300" height="180">8QFS6AC0WeI</youtube>

			== Код ==
	void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {		void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {
	visited[v] = 1;		visited[v] = 1;

Ctrlalt в 12:13, 10 февраля 2023

2023-02-10T12:13:22Z

← Предыдущая версия		Версия от 12:13, 10 февраля 2023
Строка 1:		Строка 1:
	void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {		void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {
	visited[v] = 1;		visited[v] = 1;
	for (int to : g[v]) {		for (int to : graph[v]) {
	if (!visited[to])		if (!visited[to])
	dfs(graph, to, visited);		dfs(graph, to, visited);

Ctrlalt в 18:06, 22 марта 2022

2022-03-22T18:06:57Z

← Предыдущая версия		Версия от 18:06, 22 марта 2022
Строка 1:		Строка 1:
	vector<vector<int>> ~~g(n);~~		void dfs(vector<vector<int>> &graph, int v, vector<int> &visited) {
	vector<int> visited~~(n); // 0 - ещё не были в вершине, 1 - вошли, но ещё не вышли из неё, 2 - уже обработали её~~

	~~void dfs(int v~~) {
	visited[v] = 1;		visited[v] = 1;
	for (int to : g[v]) {		for (int to : g[v]) {
	if (!visited[to])		if (!visited[to])
	dfs(to);		dfs(graph, to, visited);
	else if (visited[to] == 1)		else if (visited[to] == 1)
	/* граф содержит цикл */;		/* граф содержит цикл */;
Строка 13:		Строка 10:
	}		}

	for (int v = 0; v < n; v++)		for (int v = 0; v < graph.size(); v++)
	if (!visited[v])		if (!visited[v])
	dfs(v);		dfs(graph, v, visited);

	== Ссылки на задачи ==		== Ссылки на задачи ==

Ctrlalt в 15:33, 15 февраля 2020

2020-02-15T15:33:46Z

← Предыдущая версия		Версия от 15:33, 15 февраля 2020
Строка 13:		Строка 13:
	}		}

	for (int i = 0; i < n; i++)		for (int v = 0; v < n; v++)
	if (!visited[i])		if (!visited[v])
	dfs(i);		dfs(v);

	== Ссылки на задачи ==		== Ссылки на задачи ==

Ctrlalt: /* Ссылки */

2020-02-15T15:30:25Z

Ссылки

← Предыдущая версия		Версия от 15:30, 15 февраля 2020
Строка 26:		Строка 26:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе]
	* [http://brestprog.by/topics/graphcycles/ brestprog — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)		* [http://brestprog.by/topics/graphcycles/ brestprog — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)
	* [~~https~~://brestprog.by/topics/bipartite/ brestprog — Двудольные графы. Проверка графа на двудольность]		* [http://brestprog.by/topics/bipartite/ brestprog — Двудольные графы. Проверка графа на двудольность]
	* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]		* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]
	* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]		* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]

Ctrlalt: /* Ссылки */

2020-02-15T15:30:15Z

Ссылки

← Предыдущая версия		Версия от 15:30, 15 февраля 2020
Строка 25:		Строка 25:
	* [http://e-maxx.ru/algo/finding_cycle e-maxx.ru — Проверка графа на ацикличность и нахождение цикла]		* [http://e-maxx.ru/algo/finding_cycle e-maxx.ru — Проверка графа на ацикличность и нахождение цикла]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе]
	* [http://brestprog.~~neocities.org~~/~~lections~~/graphcycles~~.html~~ brestprog~~.neocities.org —~~ Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)		* [http://brestprog.by/topics/graphcycles/ brestprog — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)
	* [~~http~~://brestprog.~~neocities.org~~/~~lections~~/bipartite~~.html~~ brestprog~~.neocities.org —~~ Двудольные графы. Проверка графа на двудольность]		* [https://brestprog.by/topics/bipartite/ brestprog — Двудольные графы. Проверка графа на двудольность]
	* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]		* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]
	* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]		* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]

Ctrlalt в 15:28, 15 февраля 2020

2020-02-15T15:28:27Z

← Предыдущая версия		Версия от 15:28, 15 февраля 2020
Строка 1:		Строка 1:
	vector<int> g~~[V_CNT]~~;		vector<vector<int>> g(n);
	int ~~u[V_CNT]~~;		vector<int> visited(n); // 0 - ещё не были в вершине, 1 - вошли, но ещё не вышли из неё, 2 - уже обработали её

	void dfs(int v) {		void dfs(int v) {
	u[v] = 1;		visited[v] = 1;
	for (int ~~i = 0; i <~~ g[v]~~.size(); i++~~) {		for (int to : g[v]) {
	if (~~u[g~~[v][i]] == 1)		if (!visited[to])
	/* граф содержит цикл */;		dfs(to);
	~~if (!u[g[v][i]])~~		else if (visited[to] == 1)
	~~dfs(g[v][i]);~~		/* граф содержит цикл */;
	}		}
	u[v] = 2;		visited[v] = 2;
	}		}

	for (int i = 0; i < ~~V_CNT; i++)~~		for (int i = 0; i < n; i++)
	~~u[i] = 0;~~		if (!visited[i])
	~~for (int i = 0; i < V_CNT~~; i++)
	if (!u[i])
	dfs(i);		dfs(i);

Ctrlalt: /* Ссылки */

2019-08-30T13:57:45Z

Ссылки

← Предыдущая версия		Версия от 13:57, 30 августа 2019
Строка 30:		Строка 30:
	* [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность]		* [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность]
	* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]		* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]
			* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]		* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]

Ctrlalt: /* Ссылки */

2019-08-30T13:46:32Z

Ссылки

← Предыдущая версия		Версия от 13:46, 30 августа 2019
Строка 29:		Строка 29:
	* [http://brestprog.neocities.org/lections/graphcycles.html brestprog.neocities.org — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)		* [http://brestprog.neocities.org/lections/graphcycles.html brestprog.neocities.org — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)
	* [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность]		* [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность]
			* [http://algorithmica.org/tg/dfs algorithmica.org — Графы. Поиск в глубину]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]		* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]

Ctrlalt: /* Ссылки */

2016-01-27T20:02:20Z

Ссылки

← Предыдущая версия		Версия от 20:02, 27 января 2016
Строка 27:		Строка 27:
	* [http://e-maxx.ru/algo/finding_cycle e-maxx.ru — Проверка графа на ацикличность и нахождение цикла]		* [http://e-maxx.ru/algo/finding_cycle e-maxx.ru — Проверка графа на ацикличность и нахождение цикла]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%98%D1%81%D0%BF%D0%BE%D0%BB%D1%8C%D0%B7%D0%BE%D0%B2%D0%B0%D0%BD%D0%B8%D0%B5_%D0%BE%D0%B1%D1%85%D0%BE%D0%B4%D0%B0_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83_%D0%B4%D0%BB%D1%8F_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_%D1%86%D0%B8%D0%BA%D0%BB%D0%B0_%D0%B2_%D0%BE%D1%80%D0%B8%D0%B5%D0%BD%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D0%BE%D0%BC_%D0%B3%D1%80%D0%B0%D1%84%D0%B5 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска цикла в ориентированном графе]
			* [http://brestprog.neocities.org/lections/graphcycles.html brestprog.neocities.org — Проверка графа на наличие циклов] (рассматриваются циклы в неориентированных графах)
			* [http://brestprog.neocities.org/lections/bipartite.html brestprog.neocities.org — Двудольные графы. Проверка графа на двудольность]
	* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]		* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]		* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. Поиск в глубину]