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	11 ms	16 MB
g++	large_cycle_00	AC	2864 ms	333 MB
g++	max_random_00	AC	1701 ms	129 MB
g++	max_random_01	AC	1672 ms	129 MB
g++	max_random_02	AC	1677 ms	129 MB
g++	max_random_03	AC	1650 ms	129 MB
g++	max_random_04	AC	1723 ms	128 MB
g++	random_00	AC	1349 ms	106 MB
g++	random_01	AC	1472 ms	116 MB
g++	random_02	AC	2310 ms	71 MB
g++	random_03	AC	717 ms	77 MB
g++	random_04	AC	637 ms	64 MB
clang++	example_00	AC	12 ms	14 MB
clang++	large_cycle_00	AC	610 ms	106 MB
clang++	max_random_00	AC	1365 ms	128 MB
clang++	max_random_01	AC	1405 ms	128 MB
clang++	max_random_02	AC	1353 ms	126 MB
clang++	max_random_03	AC	1370 ms	128 MB
clang++	max_random_04	AC	1459 ms	128 MB
clang++	random_00	AC	1075 ms	105 MB
clang++	random_01	AC	1204 ms	117 MB
clang++	random_02	AC	323 ms	45 MB
clang++	random_03	AC	553 ms	77 MB
clang++	random_04	AC	459 ms	65 MB

Back to top page