connectedComponents (連結成分分解 simple ver)
(src/graph/simple/connectedComponents.hpp)

• View this file on GitHub
• Last update: 2023-02-15 00:30:59+09:00
• Include: #include "src/graph/simple/connectedComponents.hpp"

概要

与えられた無向グラフ $G(V, E)$ を連結成分に分解します。

ある頂点の二つ組 $(u, v)$ $u \in V, v \in V$ について、 $u$ から $v$ へのパスが存在する時またその時に限り $u$ と $v$ は同じ連結成分に属します。

機能

コンストラクタ

zawa::connectedComponents(const std::vector<std::vector<int>>& G)

zawa::connectedComponents<cost_type> cc(const std::vector<std::vector<std::pair<int, cost_type>>>& G)

• G: グラフの隣接リストを表すstd::vector<std::vector<int>>
  • zawa::read_graphを用いるとAtCoderの入力形式から対応するGを作ることができます
  • 重み付きグラフの場合はstd::vector<std::vector<std::pair<int, cost_type>>>です。
• 計算量: $O(\mid V\mid + \mid E\mid)$

オペレータ

inline std::vector<int> operator[](int i) const

• 頂点 $i$ が含まれる連結成分のidを返します。
• $0\ \le\ i\ <\ \mid V\mid$

メンバ関数

inline std::size_t size() const

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

inline std::size_t size(int x) const

• 頂点xが属する連結成分の頂点数を返します。
• 単体テストをまだしていません

inline std::vector<std::vector<int>> comps() const

• 連結成分の分解状況を返します。
  • AC Library dsu のgroupsと同じノリです
  • 頂点番号に対して昇順に並んでいます

inline std::vector<int> comp(int id) const

• id が振られた連結成分の頂点集合を返します。
  • cc.comps()[id]と等価です。
  • 単体テストをまだしていません

bool same(int i, int j) const

• 頂点 $i$ と頂点 $j$ が同じ連結成分に属するかを判定します。
  • cc[i] == cc[j]と等価です。
• 計算量 $O(1)$

Verified with

• test/ABC199-D.test.cpp
• test/ABC282-D.test.cpp
• test/ABC284-C.test.cpp
• test/ABC289-B.test.cpp
• test/connectedComponents1.test.cpp

Code

#pragma once

#include <vector>
#include <stack>

namespace zawa {

class connectedComponents {
private:
	std::vector<int> ids;
	std::vector<std::vector<int>> groups;    

	void build(const std::vector<std::vector<int>>& G) {
		int id = 0;
		for (int i = 0 ; i < (int)G.size() ; i++) {
			if (ids[i] == -1) {
				ids[i] = id;
				std::stack<int> stk({ i });		
				while (stk.size()) {
					int v = stk.top();
					stk.pop();
					for (auto x : G[v]) {
						if (ids[x] == -1) {
							ids[x] = id;
							stk.push(x);
						}
					}
				}
				id++;
			}
		}
		groups = std::vector(id, std::vector(0, 0));
		for (int i = 0 ; i < (int)ids.size() ; i++) {
			groups[ids[i]].push_back(i);
		}
	}

public:

	connectedComponents(const std::vector<std::vector<int>>& G) : ids(G.size(), -1) {
		build(G);
	}

	template <class cost_type>
	connectedComponents(const std::vector<std::vector<std::pair<int, cost_type>>>& G) : ids(G.size(), -1) {
		std::vector tmpG(G.size(), std::vector(0, 0));
		for (int i = 0 ; i < (int)G.size() ; i++) {
			for (auto [x, _] : G[i]) {
				tmpG[i].push_back(x);
			}
		}
		build(tmpG);
	}

	inline int operator [](int i) const {
		return ids[i];
	}

	inline std::size_t size() const {
		return groups.size();
	}

	inline std::size_t size(int x) const {
		return groups[ids[x]].size();
	}

	inline std::vector<std::vector<int>> comps() const {
		return groups;
	}

	inline std::vector<int> comp(int id) const {
		return groups[id];
	}

	bool same(int i, int j) const {
		return ids[i] == ids[j];
	}
};

} // namespace zawa

#line 2 "src/graph/simple/connectedComponents.hpp"

#include <vector>
#include <stack>

namespace zawa {

class connectedComponents {
private:
	std::vector<int> ids;
	std::vector<std::vector<int>> groups;    

	void build(const std::vector<std::vector<int>>& G) {
		int id = 0;
		for (int i = 0 ; i < (int)G.size() ; i++) {
			if (ids[i] == -1) {
				ids[i] = id;
				std::stack<int> stk({ i });		
				while (stk.size()) {
					int v = stk.top();
					stk.pop();
					for (auto x : G[v]) {
						if (ids[x] == -1) {
							ids[x] = id;
							stk.push(x);
						}
					}
				}
				id++;
			}
		}
		groups = std::vector(id, std::vector(0, 0));
		for (int i = 0 ; i < (int)ids.size() ; i++) {
			groups[ids[i]].push_back(i);
		}
	}

public:

	connectedComponents(const std::vector<std::vector<int>>& G) : ids(G.size(), -1) {
		build(G);
	}

	template <class cost_type>
	connectedComponents(const std::vector<std::vector<std::pair<int, cost_type>>>& G) : ids(G.size(), -1) {
		std::vector tmpG(G.size(), std::vector(0, 0));
		for (int i = 0 ; i < (int)G.size() ; i++) {
			for (auto [x, _] : G[i]) {
				tmpG[i].push_back(x);
			}
		}
		build(tmpG);
	}

	inline int operator [](int i) const {
		return ids[i];
	}

	inline std::size_t size() const {
		return groups.size();
	}

	inline std::size_t size(int x) const {
		return groups[ids[x]].size();
	}

	inline std::vector<std::vector<int>> comps() const {
		return groups;
	}

	inline std::vector<int> comp(int id) const {
		return groups[id];
	}

	bool same(int i, int j) const {
		return ids[i] == ids[j];
	}
};

} // namespace zawa

Back to top page