mmrz's library

This documentation is automatically generated by online-judge-tools/verification-helper

---

Project maintained by mm-rz Hosted on GitHub Pages — Theme by mattgraham

強連結成分分解
(graph/strongly_connected_components.hpp)

• View this file on GitHub
• Last update: 2025-07-01 03:22:56+09:00
• Include: #include "graph/strongly_connected_components.hpp"

強連結成分分解

使い方

グラフ $G$ は頂点数 $N$, 辺数 $M$ の有向グラフとする。

• scc_graph(n) : 頂点数 $N$ の有向グラフを定義する
• add_edge(int a, int b) : $a$ から $b$ へ向かう辺を追加する
• vector<vector<int>> scc() : 強連結成分分解をする。トポロジカルソートされた強連結成分・その強連結成分に属する頂点集合を返す。 $O(N+M)$

Required by

• 2-SAT (graph/two_sat.hpp)

Verified with

• verify/aoj/grl/3_C.test.cpp
• verify/aoj/id/3205.test.cpp
• verify/yosupo/scc.test.cpp
• verify/yosupo/two_sat.test.cpp
• verify/yukicoder/274.test.cpp
• verify/yukicoder/2780.test.cpp

Code

#pragma once

#include<vector>

struct scc_graph {
	int n;
	int k;
	std::vector<std::vector<int>> g;
	std::vector<std::vector<int>> rg;
	std::vector<bool> used;
	std::vector<int> cmp;
	std::vector<int> vs;

	scc_graph(int _n) : n(_n), k(0), g(n), rg(n), used(n), cmp(n) {}

	void add_edge(int a, int b) {
		g[a].push_back(b);
		rg[b].push_back(a);
	}

	void dfs(int v){
		used[v] = true;
		for(auto to : g[v]){
			if(not used[to])dfs(to);
		}
		vs.push_back(v);
	}

	void rdfs(int v, int col){
		used[v] = true;
		cmp[v] = col;
		for(auto to : rg[v]){
			if(not used[to])rdfs(to, col);
		}
	}

	std::vector<std::vector<int>> scc() {
		for(int i = 0;i < n;i++){
			if(not used[i])dfs(i);
		}
		for(int i = 0;i < n;i++){
			used[i] = false;
		}
		for(auto i = vs.rbegin();i != vs.rend();i++){
			if(not used[*i])rdfs(*i, k++);
		}
		std::vector<std::vector<int>> ret(k);
		for(int i = 0;i < n;i++){
			ret[cmp[i]].push_back(i);
		}
		return ret;
	}
};

#line 2 "graph/strongly_connected_components.hpp"

#include<vector>

struct scc_graph {
	int n;
	int k;
	std::vector<std::vector<int>> g;
	std::vector<std::vector<int>> rg;
	std::vector<bool> used;
	std::vector<int> cmp;
	std::vector<int> vs;

	scc_graph(int _n) : n(_n), k(0), g(n), rg(n), used(n), cmp(n) {}

	void add_edge(int a, int b) {
		g[a].push_back(b);
		rg[b].push_back(a);
	}

	void dfs(int v){
		used[v] = true;
		for(auto to : g[v]){
			if(not used[to])dfs(to);
		}
		vs.push_back(v);
	}

	void rdfs(int v, int col){
		used[v] = true;
		cmp[v] = col;
		for(auto to : rg[v]){
			if(not used[to])rdfs(to, col);
		}
	}

	std::vector<std::vector<int>> scc() {
		for(int i = 0;i < n;i++){
			if(not used[i])dfs(i);
		}
		for(int i = 0;i < n;i++){
			used[i] = false;
		}
		for(auto i = vs.rbegin();i != vs.rend();i++){
			if(not used[*i])rdfs(*i, k++);
		}
		std::vector<std::vector<int>> ret(k);
		for(int i = 0;i < n;i++){
			ret[cmp[i]].push_back(i);
		}
		return ret;
	}
};

Back to top page