Компоненты сильной связности. Алгоритм Косараю-Шарира - История изменений

Ctrlalt в 15:33, 30 июня 2023

2023-06-30T15:33:10Z

← Предыдущая версия		Версия от 15:33, 30 июня 2023
Строка 11:		Строка 11:
	struct Graph {		struct Graph {
	vector<vector<int>> graph, graphR;		vector<vector<int>> graph, graphR;
	vector<int> visited, order;		vector<int> visited, order, sccOf;

	Graph(int vertexCount) :		Graph(int vertexCount) :
Строка 30:		Строка 30:

	void dfs2(int v, int component) {		void dfs2(int v, int component) {
	~~visited~~[v] = component;		sccOf[v] = component;
	for (int to : graphR[v])		for (int to : graphR[v])
	if (~~!visited~~[to])		if (sccOf[to] == -1)
	dfs2(to, component);		dfs2(to, component);
	}		}
Строка 43:		Строка 43:
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());

	~~visited~~.assign(graph.size(), 0);		sccOf.assign(graph.size(), -1);
	int sccCount = 0;		int sccCount = 0;
	for (int v : order)		for (int v : order)
	if (~~!visited~~[v])		if (sccOf[v] == -1)
	dfs2(v, ++~~sccCount~~);		dfs2(v, sccCount++);

	return ~~visited~~;		return sccOf;
	}		}
	};		};
Строка 56:		Строка 56:
	struct Graph {		struct Graph {
	vector<vector<int>> graph, graphR;		vector<vector<int>> graph, graphR;
	vector<int> visited, order;		vector<int> visited, order, sccOf;

	Graph(int vertexCount) :		Graph(int vertexCount) :
Строка 75:		Строка 75:

	void dfs2(int v, int component) {		void dfs2(int v, int component) {
	~~visited~~[v] = component;		sccOf[v] = component;
	for (int to : graphR[v])		for (int to : graphR[v])
	if (~~!visited~~[to])		if (sccOf[to] == -1)
	dfs2(to, component);		dfs2(to, component);
	}		}
Строка 88:		Строка 88:
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());

	~~visited~~.assign(graph.size(), 0);		sccOf.assign(graph.size(), -1);
	int sccCount = 0;		int sccCount = 0;
	for (int v : order)		for (int v : order)
	if (~~!visited~~[v])		if (sccOf[v] == -1)
	dfs2(v, ++~~sccCount~~);		dfs2(v, sccCount++);

	vector<set<int>> graphC(sccCount);		vector<set<int>> graphC(sccCount);
	for (int v = 0; v < graph.size(); v++)		for (int v = 0; v < graph.size(); v++)
	for (int to : graph[v])		for (int to : graph[v])
	if (~~visited~~[v] != ~~visited~~[to])		if (sccOf[v] != sccOf[to])
	graphC[~~visited~~[v]].insert(~~visited~~[to]);		graphC[sccOf[v]].insert(sccOf[to]);

	return graphC;		return graphC;

Ctrlalt в 15:21, 30 июня 2023

2023-06-30T15:21:13Z

Внесённые изменения

Ctrlalt в 15:17, 24 мая 2023

2023-05-24T15:17:26Z

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

			== Код ==
	* Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).		* Упорядочиваем вершины по убыванию времени выхода (как при топологической сортировке).
	* Транспонируем граф.		* Транспонируем граф.

Ctrlalt в 07:16, 8 июля 2021

2021-07-08T07:16:21Z

← Предыдущая версия		Версия от 07:16, 8 июля 2021
Строка 36:		Строка 36:
	Построение конденсации:		Построение конденсации:

	~~unordered_map~~<int, ~~vector~~<int>> ~~graph~~, ~~graphR~~, ~~graphC~~;		struct Graph {
	~~unordered_set~~<int> visited;		int vertexCount, sccCount;
	vector<int> order;		map<int, set<int>> g, gr, gc;
			set<int> visited;
			vector<int> order;
			map<int, int> sccIndexOf, sccSize;

	~~void dfs1~~(int ~~v) {~~		Graph(int vertexCount) : vertexCount(vertexCount), sccCount(0) {}
	~~visited.insert(v~~);
	~~for (int to~~ : ~~graph[v])~~
	~~if (!visited.count~~(~~to)~~)
	~~dfs1~~(to);
	~~order.push_back(v);~~
	}

	~~unordered_map<~~int, int~~> scc~~;		void addEdge(int a, int b) {
			g[a].insert(b);
			gr[b].insert(a);
			}

	void ~~dfs2~~(int v~~, int component~~) {		void dfs1(int v) {
	visited.insert(v);		visited.insert(v);
	~~scc[v] = component;~~		for (int to : g[v])
	for (int to : ~~graphR~~[v]) {		if (!visited.count(to))
	if (!visited.count(to))		dfs1(to);
	~~dfs2~~(to~~, component~~);		order.push_back(v);
	}		}
	}

	int ~~main~~() {		void dfs2(int v, int component) {
	~~int vertexCount~~, ~~edgeCount~~;		visited.insert(v);
	~~cin >> vertexCount >> edgeCount;~~		sccIndexOf[v] = component;
			sccSize[component]++;
			for (int to : gr[v]) {
			if (!visited.count(to))
			dfs2(to, component);
			}
			}

	~~for~~ (~~int i = 0; i < edgeCount; i++~~) {		void condense() {
	~~int a, b;~~		for (int v = 0; v < vertexCount; v++)
	~~cin >> a >> b;~~		if (!visited.count(v))
	~~graph[a].push_back(b);~~		dfs1(v);
	~~graphR[b].push_back(a);~~		reverse(order.begin(), order.end());
	}

	for (int v = 0; v < vertexCount; v++)
	if (!visited.count(v))
	dfs1(v);
	reverse(order.begin(), order.end());

	visited.clear();		visited.clear();
	~~int sccN = 0;~~		for (int v : order)
	for (int v : order)		if (!visited.count(v))
	if (!visited.count(v))		dfs2(v, sccCount++);
	dfs2(v, ~~sccN~~++);

	for (int v = 0; v < vertexCount; v++)		for (int v = 0; v < vertexCount; v++)
	for (int to : ~~graph~~[v])		for (int to : g[v])
	if (~~scc~~[v] != ~~scc~~[to])		if (sccIndexOf[v] != sccIndexOf[to])
	~~graphC~~[~~scc~~[v]].~~push_back~~(~~scc~~[to]);		gc[sccIndexOf[v]].insert(sccIndexOf[to]);
	}		}
			};

	== Ссылки ==		== Ссылки ==

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

2021-04-12T15:05:37Z

Ссылки

← Предыдущая версия		Версия от 15:05, 12 апреля 2021
Строка 88:		Строка 88:

	== Ссылки ==		== Ссылки ==
	* [http://e-maxx.ru/algo/strong_connected_components 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_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска компонент сильной связности]		:* [http://e-maxx.ru/algo/strong_connected_components e-maxx.ru — Поиск компонент сильной связности, построение конденсации графа]
	* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]		:* [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_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска компонент сильной связности]
	* [~~http~~://~~informatics~~.~~mccme~~.ru/~~course~~/~~view~~.~~php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]~~		:* [http://algorithmica.org/tg/dfs-plus algorithmica.org — Продвинутый DFS]
	* [http://github.com/petr-kalinin/progtexts/releases/download/v2014.11.01/04_dfs.pdf Калинин П. ~~Поиск в глубину~~]		:* [https://notes.algoprog.ru/dfs/04_3_topsort.html#id5 Калинин П. Компоненты сильной связности]
	* [~~http~~://ejudge.~~btty~~.su/~~bmstu~~/~~addon~~/~~docs~~/~~articles~~/~~moscow2006-dfs~~.pdf Лахно А. Поиск в глубину и его применение]		:* [https://ejudge.lksh.ru/archive/2014/07/Cprime/stuff/Dfs.pdf Лахно А. Поиск в глубину и его применение]
	* [~~http~~://algs4.cs.princeton.edu/lectures/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]		:* [https://algs4.cs.princeton.edu/lectures/keynote/42DirectedGraphs.pdf algs4.cs.princeton.edu/lectures — 4.2 Directed Graphs]
	* [~~http~~://visualgo.net/dfsbfs~~.html~~ VisuAlgo — Graph Traversal]		Демонстрация:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/java/~~src~~/~~SCCKosaraju~~.java ~~CodeLibrary~~ — ~~Strongly connected components. Kosaraju's algorithm~~]		:* [https://visualgo.net/en/dfsbfs VisuAlgo — Graph Traversal]
			Код:
			:* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/dfs/strongly_connected_components.cpp codelibrary/cpp/graphs/dfs/strongly_connected_components.cpp]
			:* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/KosarajuSharirSCC.java algs4/KosarajuSharirSCC.java]
			Задачи:
			:* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru — Курс «Алгоритмы на графах» — часть 2]

	[[Category:Поиск в глубину и его приложения]]		[[Category:Поиск в глубину и его приложения]]

Ctrlalt в 21:16, 7 апреля 2021

2021-04-07T21:16:42Z

← Предыдущая версия		Версия от 21:16, 7 апреля 2021
Строка 3:		Строка 3:
	* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").		* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").

	vector<vector<int>> g(n), gr(n);		vector<vector<int>> graph(vertexCount), graphR(vertexCount);
	vector<int> visited(n);		vector<int> visited(vertexCount);
	vector<int> order;		vector<int> order;

	void dfs1(int v) {		void dfs1(int v) {
	visited[v] = 1;		visited[v] = 1;
	for (int to : g[v])		for (int to : graph[v])
	if (!visited[to])		if (!visited[to])
	dfs1(to);		dfs1(to);
Строка 17:		Строка 17:
	void dfs2(int v, int component) {		void dfs2(int v, int component) {
	visited[v] = component;		visited[v] = component;
	for (int to : gr[v])		for (int to : graphR[v])
	if (!visited[to])		if (!visited[to])
	dfs2(to, component);		dfs2(to, component);
	}		}

	for (int v = 0; v < n; v++)		for (int v = 0; v < vertexCount; v++)
	if (!visited[v])		if (!visited[v])
	dfs1(v);		dfs1(v);
Строка 29:		Строка 29:
	fill(visited.begin(), visited.end(), 0);		fill(visited.begin(), visited.end(), 0);

	int ~~componentsCount~~ = 0;		int componentCount = 0;
	for (int v : order)		for (int v : order)
	if (!visited[v])		if (!visited[v])
	dfs2(v, ++~~componentsCount~~);		dfs2(v, ++componentCount);

	Построение конденсации:		Построение конденсации:

	unordered_map<int, vector<int>> g, gr, gc;		unordered_map<int, vector<int>> graph, graphR, graphC;
	unordered_set<int> visited;		unordered_set<int> visited;
	vector<int> order;		vector<int> order;
Строка 42:		Строка 42:
	void dfs1(int v) {		void dfs1(int v) {
	visited.insert(v);		visited.insert(v);
	for (int to : g[v]) {		for (int to : graph[v])
	if (!visited.count(to))		if (!visited.count(to))
	dfs1(to);		dfs1(to);
	}
	order.push_back(v);		order.push_back(v);
	}		}
Строка 54:		Строка 53:
	visited.insert(v);		visited.insert(v);
	scc[v] = component;		scc[v] = component;
	for (int to : gr[v]) {		for (int to : graphR[v]) {
	if (!visited.count(to))		if (!visited.count(to))
	dfs2(to, component);		dfs2(to, component);
Строка 61:		Строка 60:

	int main() {		int main() {
	int n, m;		int vertexCount, edgeCount;
	cin >> n >> m;		cin >> vertexCount >> edgeCount;

	for (int i = 0; i < m; i++) {		for (int i = 0; i < edgeCount; i++) {
	int a, b;		int a, b;
	cin >> a >> b;		cin >> a >> b;
	g[a].push_back(b);		graph[a].push_back(b);
	gr[b].push_back(a);		graphR[b].push_back(a);
	}		}

	for (int v = 0; v < n; v++) {		for (int v = 0; v < vertexCount; v++)
	if (!visited.count(v))		if (!visited.count(v))
	dfs1(v);		dfs1(v);
	}
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());

	visited.clear();		visited.clear();
	int sccN = 0;		int sccN = 0;
	for (int v : order) {		for (int v : order)
	if (!visited.count(v))		if (!visited.count(v))
	dfs2(v, sccN++);		dfs2(v, sccN++);
	}

	for (int v = 0; v < n; v++) {		for (int v = 0; v < vertexCount; v++)
	for (int to : g[v])		for (int to : graph[v])
	if (scc[v] != scc[to])		if (scc[v] != scc[to])
	gc[scc[v]].push_back(scc[to]);		graphC[scc[v]].push_back(scc[to]);
	}
	}		}

Ctrlalt в 14:09, 11 марта 2020

2020-03-11T14:09:47Z

← Предыдущая версия		Версия от 14:09, 11 марта 2020
Строка 65:		Строка 65:

	for (int i = 0; i < m; i++) {		for (int i = 0; i < m; i++) {
	~~string~~ a, b;		int a, b;
	cin >> a >> b;		cin >> a >> b;
	g[a].push_back(b);		g[a].push_back(b);

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

2020-02-15T16:02:21Z

← Предыдущая версия		Версия от 16:02, 15 февраля 2020
Строка 3:		Строка 3:
	* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").		* Обходим вершины транспонированного графа в порядке убывания времени выхода ("порядке топологической сортировки").

	vector<int> g~~[V_CNT]~~, ~~gR[V_CNT]~~;		vector<vector<int>> g(n), gr(n);
	int ~~u[V_CNT]~~;		vector<int> visited(n);
	vector<int> order;		vector<int> order;

	void dfs1(int v) {		void dfs1(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]~~])		if (!visited[to])
	dfs1(~~g[v][i]~~);		dfs1(to);
	order.push_back(v);		order.push_back(v);
	}		}

	void dfs2(int v, int k) {		void dfs2(int v, int component) {
	u[v] = k;		visited[v] = component;
	for (int ~~i = 0; i < gR~~[v]~~.size(); i++~~)		for (int to : gr[v])
	if (!~~u[gR~~[~~v][i]~~])		if (!visited[to])
	dfs2(~~gR[v][i]~~, k);		dfs2(to, component);
	}		}

	for (int i = 0; i < ~~V_CNT~~; ~~i++)~~		for (int v = 0; v < n; v++)
	~~u[i] = 0;~~		if (!visited[v])
	~~for (int i = 0; i < V_CNT; i~~++)		dfs1(v);
	if (!u[i])
	dfs1(i);
	reverse(order.begin(), order.end());		reverse(order.begin(), order.end());
	~~for~~ (~~int i =~~ 0; ~~i < V_CNT; i++)~~
	~~u[i] = 0;~~		fill(visited.begin(), visited.end(), 0);
	int k = 1;
	for (int ~~i = 0; i < V_CNT; i++~~)		int componentsCount = 0;
	if (!u[~~order[i]~~])		for (int v : order)
	dfs2(~~order[i]~~, k++);		if (!visited[v])
			dfs2(v, ++componentsCount);

	Построение конденсации:		Построение конденсации:

	unordered_map<int, vector<int>> g, gr, gc;		unordered_map<int, vector<int>> g, gr, gc;

	unordered_set<int> visited;		unordered_set<int> visited;
	vector<int> order;		vector<int> order;

	void dfs1(int v) {		void dfs1(int v) {
	visited.insert(v);		visited.insert(v);
Строка 51:		Строка 50:

	unordered_map<int, int> scc;		unordered_map<int, int> scc;
	void dfs2(int v, int ~~sccN~~) {
			void dfs2(int v, int component) {
	visited.insert(v);		visited.insert(v);
	scc[v] = ~~sccN~~;		scc[v] = component;
	for (int to : gr[v]) {		for (int to : gr[v]) {
	if (!visited.count(to))		if (!visited.count(to))
	dfs2(to, ~~sccN~~);		dfs2(to, component);
	}		}
	}		}
Строка 79:		Строка 79:
	visited.clear();		visited.clear();
	int sccN = 0;		int sccN = 0;
	for (int ~~i = 0; i <~~ order~~.size(); i++~~) {		for (int v : order) {
	if (!visited.count(~~order[i]~~))		if (!visited.count(v))
	dfs2(~~order[i]~~, sccN++);		dfs2(v, sccN++);
	}		}

Ctrlalt в 13:58, 30 августа 2019

2019-08-30T13:58:04Z

← Предыдущая версия		Версия от 13:58, 30 августа 2019
Строка 94:		Строка 94:
	* [http://e-maxx.ru/algo/strong_connected_components e-maxx.ru — Поиск компонент сильной связности, построение конденсации графа]		* [http://e-maxx.ru/algo/strong_connected_components 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_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 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_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82_%D1%81%D0%B8%D0%BB%D1%8C%D0%BD%D0%BE%D0%B9_%D1%81%D0%B2%D1%8F%D0%B7%D0%BD%D0%BE%D1%81%D1%82%D0%B8 neerc.ifmo.ru/wiki — Использование обхода в глубину для поиска компонент сильной связности]
			* [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 в 13:01, 11 июня 2019

2019-06-11T13:01:57Z

@@ Строка 34: / Строка 34: @@
       if (!u[order[i]])
           dfs2(order[i], k++);
 == Ссылки ==