test/graph/strongly_connected_components/yosupo_scc.test.cpp

• View this file on GitHub
• Last update: 2024-11-09 18:06:54+09:00
• Problem: https://judge.yosupo.jp/problem/scc

Depends on

• Strongly Connected Components (src/graph/strongly_connected_components.hpp)

Code

// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

#include "src/graph/strongly_connected_components.hpp"

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	StronglyConnectedComponents scc(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		scc.add_edge(a, b);
	}

	int k = scc.build();
	vector<vector<int>> groups(k);
	for (int i = 0; i < n; ++i) groups[scc.component_id(i)].push_back(i);

	cout << k << endl;
	for (auto const &group : groups) {
		cout << group.size();
		for (auto const &v : group) cout << " " << v;
		cout << endl;
	}

	return 0;
}

#line 1 "test/graph/strongly_connected_components/yosupo_scc.test.cpp"
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc

#line 1 "src/graph/strongly_connected_components.hpp"



#include <algorithm>
#include <vector>

class StronglyConnectedComponents {
private:
	int n;
	std::vector<std::vector<int>> graph, rev_graph;
	std::vector<int> components;

	void dfs(int v, std::vector<bool> &used, std::vector<int> &order) {
		if (used[v]) return;
		used[v] = true;
		for (auto const &nv : graph[v]) dfs(nv, used, order);
		order.push_back(v);
	}

	void rev_dfs(int v, int id, std::vector<int> &components) {
		if (components[v] != -1) return;
		components[v] = id;
		for (auto const &nv : rev_graph[v]) rev_dfs(nv, id, components);
	}

public:
	StronglyConnectedComponents(int n) : n(n), graph(n), rev_graph(n), components(n) {}

	void add_edge(int from, int to) {
		graph[from].push_back(to);
		rev_graph[to].push_back(from);
	}

	int build() {
		std::vector<bool> used(n);
		std::vector<int> order(n);
		for (int i = 0; i < n; ++i) {
			if (used[i]) continue;
			dfs(i, used, order);
		}
		std::reverse(order.begin(), order.end());

		int cnt = 0;
		components.assign(n, -1);
		for (auto const &v : order) {
			if (components[v] != -1) continue;
			rev_dfs(v, cnt, components);
			++cnt;
		}

		return cnt;
	}

	int component_id(int v) { return components[v]; }
};


#line 4 "test/graph/strongly_connected_components/yosupo_scc.test.cpp"

#include <iostream>
#line 7 "test/graph/strongly_connected_components/yosupo_scc.test.cpp"

using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	StronglyConnectedComponents scc(n);
	for (int i = 0; i < m; ++i) {
		int a, b;
		cin >> a >> b;
		scc.add_edge(a, b);
	}

	int k = scc.build();
	vector<vector<int>> groups(k);
	for (int i = 0; i < n; ++i) groups[scc.component_id(i)].push_back(i);

	cout << k << endl;
	for (auto const &group : groups) {
		cout << group.size();
		for (auto const &v : group) cout << " " << v;
		cout << endl;
	}

	return 0;
}

Test cases

Env	Name	Status	Elapsed	Memory
g++	example_00	AC	12 ms	16 MB
g++	large_cycle_00	AC	2921 ms	334 MB
g++	max_random_00	AC	1747 ms	131 MB
g++	max_random_01	AC	1775 ms	130 MB
g++	max_random_02	AC	1778 ms	131 MB
g++	max_random_03	AC	1851 ms	131 MB
g++	max_random_04	AC	1796 ms	130 MB
g++	random_00	AC	1459 ms	108 MB
g++	random_01	AC	1539 ms	118 MB
g++	random_02	AC	2348 ms	72 MB
g++	random_03	AC	721 ms	80 MB
g++	random_04	AC	618 ms	64 MB
clang++	example_00	AC	13 ms	14 MB
clang++	large_cycle_00	AC	611 ms	111 MB
clang++	max_random_00	AC	1541 ms	128 MB
clang++	max_random_01	AC	1500 ms	126 MB
clang++	max_random_02	AC	1458 ms	126 MB
clang++	max_random_03	AC	1485 ms	126 MB
clang++	max_random_04	AC	1473 ms	130 MB
clang++	random_00	AC	1135 ms	103 MB
clang++	random_01	AC	1290 ms	115 MB
clang++	random_02	AC	355 ms	45 MB
clang++	random_03	AC	583 ms	76 MB
clang++	random_04	AC	491 ms	62 MB

Back to top page