強連結成分分解 (SCC)
(GraphTheory/StronglyConnectedComponents.hpp)

View this file on GitHub
Last update: 2021-03-13 10:43:13+09:00
Include: #include "GraphTheory/StronglyConnectedComponents.hpp"
Link: https://tkmst201.github.io/Library/GraphTheory/StronglyConnectedComponents.hpp

概要

有向グラフを強連結成分分解します。
強連結成分分解についてはページ下部にある参考リンク先を参照してください。

StronglyConnectedComponents(const Graph & g)
- $\Theta(N + M)$ グラフ g で初期化
int size()
- $\Theta(1)$ グラフの頂点数 $N$ を返す
int scc_size()
- $\Theta(1)$ 強連結成分の個数を返す
int scc_size(int k)
- $\Theta(1)$ トポロジカル順序 $k$ の強連結成分に含まれる頂点数を返す
int rank(int u)
- $\Theta(1)$ 頂点 $u$ が含まれる強連結成分のトポロジカル順序を返す
const std::vector<int> & rank_list(int k)
- $\Theta(1)$ トポロジカル順序 $k$ の強連結成分に含まれる頂点番号を昇順に格納した配列を返す
Graph get_graph(const Graph & g)
- $\mathcal{O}((N + M) \log{(N + M)})$ 強連結成分を $1$ つの頂点に縮約したグラフを返す

コンストラクタ

以下、頂点数を $N$ 、辺の数を $M$ とします。

StronglyConnectedComponents(const Graph & g)

グラフ g で初期化します。

計算量

$\Theta(N + M)$

メンバ関数

int size()

グラフの頂点数 $N$ を返します。

計算量

$\Theta(1)$

int scc_size()

強連結成分の個数を返します。

計算量

$\Theta(1)$

int scc_size(int k)

トポロジカル順序 $k$ の強連結成分に含まれる頂点数を返します。トポロジカル順序は $0$ からカウントされます。

制約

$0 \leq k <$ scc_size()

計算量

$\Theta(1)$

int rank(int u)

頂点 $u$ が含まれる強連結成分のトポロジカル順序を返します。

制約

$0 \leq u < N$

計算量

$\Theta(1)$

const std::vector<int> & rank_list(int k)

トポロジカル順序 $k$ の強連結成分に含まれる頂点番号を昇順に格納した配列を返します。

制約

$0 \leq k <$ scc_size()

計算量

$\Theta(1)$

Graph get_graph(const Graph & g)

強連結成分を $1$ つの頂点に縮約したグラフを返します。各頂点の番号はその強連結成分のトポロジカル順序と一致します。

制約

g はコンストラクタに渡したものと同一

計算量

$\mathcal{O}((N + M) \log{(N + M)})$

使用例

#include <bits/stdc++.h>
#include "GraphTheory/StronglyConnectedComponents.hpp"
using namespace std;

int main() {
	StronglyConnectedComponents::Graph g(7);
	g[1].emplace_back(2);
	g[2].emplace_back(3);
	g[3].emplace_back(1);
	g[3].emplace_back(4);
	g[0].emplace_back(4);
	g[4].emplace_back(5);
	g[5].emplace_back(6);
	g[6].emplace_back(5);
	StronglyConnectedComponents scc(g);
	
	cout << "size() = " << scc.size() << endl; // 7
	cout << "scc_size() = " << scc.scc_size() << endl; // 4
	
	/*
		topological order 0 : 1 2 3
		topological order 1 : 0
		topological order 2 : 4
		topological order 3 : 5 6
	*/
	for (int i = 0; i < scc.scc_size(); ++i) {
		cout << "topological order " << i << " : ";
		for (int j = 0; j < scc.scc_size(i); ++j) cout << scc.rank_list(i)[j] << " \n"[j + 1 == scc.scc_size(i)];
	}
	
	cout << "rank : ";
	// 1 0 0 0 2 3 3
	for (int i = 0; i < scc.size(); ++i) cout << scc.rank(i) << " \n"[i + 1 == scc.size()];
	
	auto sccg = scc.get_graph(g);
	cout << "size = " << sccg.size() << endl; // 4
	/*
		i = 0 : 2
		i = 1 : 2
		i = 2 : 3
		i = 3 :
	*/
	for (int i = 0; i < sccg.size(); ++i) {
		cout << "i = " << i << " : ";
		for (int j = 0; j < sccg[i].size(); ++j) cout << sccg[i][j] << " \n"[j + 1 == sccg[i].size()];
	}
}

TODO

TODO: low-link を用いたより速そうな処理に変更する

参考

2020/08/27: https://mathtrain.jp/kyorenketsu

Required by

2-SAT (Mathematics/TwoSat.hpp)

Verified with

Code

#ifndef INCLUDE_GUARD_STRONGLY_CONNECTED_COMPONENTS_HPP
#define INCLUDE_GUARD_STRONGLY_CONNECTED_COMPONENTS_HPP

#include <vector>
#include <cassert>
#include <algorithm>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/StronglyConnectedComponents.hpp
 */
struct StronglyConnectedComponents {
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n;
	std::vector<int> rank_;
	std::vector<std::vector<int>> rank_list_;
	
public:
	explicit StronglyConnectedComponents(const Graph & g) : n(g.size()) {
		Graph rg(n);
		for (int i = 0; i < n; ++i) {
			for (int j : g[i]) {
				assert(0 <= j && j < n);
				rg[j].emplace_back(i);
			}
		}
		std::vector<bool> visited(n, false);
		std::vector<int> num;
		auto dfs = [&](auto self, int u) -> void {
			visited[u] = true;
			for (int v : g[u]) if (!visited[v]) self(self, v);
			num.emplace_back(u);
		};
		for (int i = 0; i < n; ++i) if (!visited[i]) dfs(dfs, i);
		int cnt = 0;
		visited.assign(n, false);
		rank_.assign(n, -1);
		auto rdfs = [&](auto self, int u) -> void {
			visited[u] = true;
			rank_[u] = cnt;
			for (int v : rg[u]) if (!visited[v]) self(self, v);
		};
		for (int i = n - 1; i >= 0; --i) if (!visited[num[i]]) rdfs(rdfs, num[i]), ++cnt;
		rank_list_.assign(cnt, {});
		for (int i = 0; i < n; ++i) rank_list_[rank_[i]].emplace_back(i);
	}
	
	int size() const noexcept {
		return n;
	}
	
	int scc_size() const noexcept {
		return rank_list_.size();
	}
	
	int scc_size(int k) const noexcept {
		assert(0 <= k && k < scc_size());
		return rank_list_[k].size();
	}
	
	int rank(int u) const noexcept {
		assert(0 <= u && u < size());
		return rank_[u];
	}
	
	const std::vector<int> & rank_list(int k) const noexcept {
		assert(0 <= k && k < scc_size());
		return rank_list_[k];
	}
	
	Graph get_graph(const Graph & g) const {
		Graph res(scc_size());
		for (int i = 0; i < scc_size(); ++i) {
			for (int j : rank_list_[i]) for (int v : g[j]) if (rank(v) != i) res[i].emplace_back(rank(v));
			std::sort(begin(res[i]), end(res[i]));
			res[i].erase(unique(begin(res[i]), end(res[i])), end(res[i]));
		}
		return res;
	}
};

#endif // INCLUDE_GUARD_STRONGLY_CONNECTED_COMPONENTS_HPP

#line 1 "GraphTheory/StronglyConnectedComponents.hpp"



#include <vector>
#include <cassert>
#include <algorithm>

/**
 * @brief https://tkmst201.github.io/Library/GraphTheory/StronglyConnectedComponents.hpp
 */
struct StronglyConnectedComponents {
	using Graph = std::vector<std::vector<int>>;
	
private:
	int n;
	std::vector<int> rank_;
	std::vector<std::vector<int>> rank_list_;
	
public:
	explicit StronglyConnectedComponents(const Graph & g) : n(g.size()) {
		Graph rg(n);
		for (int i = 0; i < n; ++i) {
			for (int j : g[i]) {
				assert(0 <= j && j < n);
				rg[j].emplace_back(i);
			}
		}
		std::vector<bool> visited(n, false);
		std::vector<int> num;
		auto dfs = [&](auto self, int u) -> void {
			visited[u] = true;
			for (int v : g[u]) if (!visited[v]) self(self, v);
			num.emplace_back(u);
		};
		for (int i = 0; i < n; ++i) if (!visited[i]) dfs(dfs, i);
		int cnt = 0;
		visited.assign(n, false);
		rank_.assign(n, -1);
		auto rdfs = [&](auto self, int u) -> void {
			visited[u] = true;
			rank_[u] = cnt;
			for (int v : rg[u]) if (!visited[v]) self(self, v);
		};
		for (int i = n - 1; i >= 0; --i) if (!visited[num[i]]) rdfs(rdfs, num[i]), ++cnt;
		rank_list_.assign(cnt, {});
		for (int i = 0; i < n; ++i) rank_list_[rank_[i]].emplace_back(i);
	}
	
	int size() const noexcept {
		return n;
	}
	
	int scc_size() const noexcept {
		return rank_list_.size();
	}
	
	int scc_size(int k) const noexcept {
		assert(0 <= k && k < scc_size());
		return rank_list_[k].size();
	}
	
	int rank(int u) const noexcept {
		assert(0 <= u && u < size());
		return rank_[u];
	}
	
	const std::vector<int> & rank_list(int k) const noexcept {
		assert(0 <= k && k < scc_size());
		return rank_list_[k];
	}
	
	Graph get_graph(const Graph & g) const {
		Graph res(scc_size());
		for (int i = 0; i < scc_size(); ++i) {
			for (int j : rank_list_[i]) for (int v : g[j]) if (rank(v) != i) res[i].emplace_back(rank(v));
			std::sort(begin(res[i]), end(res[i]));
			res[i].erase(unique(begin(res[i]), end(res[i])), end(res[i]));
		}
		return res;
	}
};

強連結成分分解 (SCC) (GraphTheory/StronglyConnectedComponents.hpp)

概要

コンストラクタ

StronglyConnectedComponents(const Graph & g)

メンバ関数

int size()

int scc_size()

int scc_size(int k)

int rank(int u)

const std::vector<int> & rank_list(int k)

Graph get_graph(const Graph & g)

使用例

TODO

参考

Required by

Verified with

Code

強連結成分分解 (SCC)
(GraphTheory/StronglyConnectedComponents.hpp)