tests/tarjan_scc.test.cpp

View this file on GitHub
Last update: 2024-02-01 17:43:59-05:00
Problem: https://judge.yosupo.jp/problem/scc

Depends on

Code

#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include "../content/graph/tarjan.h"

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);

	int n, m;
	cin >> n >> m;
	SCC t(n);
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		if (a != b)
			t.addedge(a, b);
	}
	t.run();
	cout << size(t.comps) << '\n';
	reverse(all(t.comps));
	for (auto &&v : t.comps) {
		cout << size(v);
		for (auto i : v)
			cout << ' ' << i;
		cout << '\n';
	}
}

#line 1 "tests/tarjan_scc.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#line 1 "content/utils/template.h"
/**
 * @brief My starter code
 */

#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define makeunique(x) (x).erase(unique((x).begin(), (x).end()), (x).end());

#ifdef LOCAL
template<typename T> void pr(T a){std::cerr<<a<<std::endl;}
template<typename T, typename... Args> void pr(T a, Args... args){std::cerr<<a<<' ',pr(args...);}
#else
template<typename... Args> void pr(Args... args){}
#endif

using namespace std;
using ll = long long;
using pii = pair<int, int>;
#line 3 "content/graph/tarjan.h"

/**
 * @brief Tarjan's algorithm
 * @docs docs/tarjan.md
 */

struct SCC {
	int n, t, ii;
	vector<vector<int>> adj;
	vector<int> dfn, low, id;
	vector<bool> ins;
	stack<int> stk;
	vector<vector<int>> comps;
	
	SCC(int mm) : n(mm), t(0), ii(0), adj(mm), dfn(mm), low(mm), id(mm), ins(mm) {}
	
	void addedge(int a, int b) {
		adj[a].emplace_back(b);
	}

	void dfs(int cur) {
		dfn[cur] = low[cur] = ++t;
		stk.push(cur);
		ins[cur] = 1;

		for (int u: adj[cur]) {
			if (!dfn[u]) {
				dfs(u);
				low[cur] = min(low[cur], low[u]);
			}
			else if (ins[u])
				low[cur] = min(low[cur], dfn[u]);
		}
		
		if (dfn[cur] == low[cur]) {
			int u = -1;
			comps.emplace_back();
			while (u != cur) {
				u = stk.top(); stk.pop();
				ins[u] = 0;
				id[u] = cur;
				comps.back().emplace_back(u);
			}
		}
	}

	void run() {
		for (int i = 0; i < n; i++) {
			if (!dfn[i]) {
				dfs(i);
			}
		}
	}
};

// Any connected graph decomposes into a tree of **biconnected components (BCCs)** called the **block-cut** tree of the graph
struct blockcut {
	int n, t, ei, ncomps;
	vector<vector<pii>> adj;
	vector<vector<int>> adj2, comps;
	vector<int> dfn, low, id;
	vector<bool> ins;
	stack<int> st;
	set<int> art;
	
	blockcut(int mm) : n(mm), t(0), ei(0), ncomps(0), adj(mm), comps(mm), dfn(mm), low(mm), id(mm), ins(mm) {}
	
	void addedge(int a, int b) {
		adj[a].emplace_back(b, ei);
		adj[b].emplace_back(a, ei);
		ei++;
	}

	void process(int cur){
		if (st.empty()) return;
		while (st.size()) {
			int u = st.top(); st.pop();
			comps[ncomps].push_back(u);
			if (u == cur)
				break;
		}
		ncomps++;
	}

	void dfs(int cur, int pi = -1) {
		dfn[cur] = low[cur] = ++t;
		st.push(cur);
		int ch = 0;
		for (auto [u, i]: adj[cur]) {
			if (i == pi) continue;
			if (!dfn[u]) {
				ch++;
				dfs(u, i);
				low[cur] = min(low[cur], low[u]);
				
				if ((pi == -1 and ch > 1) or (pi != -1 and low[u] >= dfn[cur])) {
					art.insert(cur);
					st.push(cur);
					process(u);
				}
			}
			else
				low[cur] = min(low[cur], dfn[u]);
		}
	}

	// Block leaders are numbered [n, n + ncomps)
	int run() {
		for (int i = 0; i < n; i++) {
			if (!dfn[i]) {
				dfs(i, -1);
				st.push(i);
				process(-1); // pop stack until empty
			}
		}
		comps.resize(ncomps);
		adj2.resize(n+ncomps);
		for (int i = 0; i < ncomps; i++) {
			sort(all(comps[i]));
			makeunique(comps[i]);
			for (int u: comps[i]) {
				adj2[n+i].push_back(u);
				adj2[u].push_back(n+i);
			}
		}
		return n + ncomps;
	}
};

#line 3 "tests/tarjan_scc.test.cpp"

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin.exceptions(cin.failbit);

	int n, m;
	cin >> n >> m;
	SCC t(n);
	for (int i = 0, a, b; i < m; i++) {
		cin >> a >> b;
		if (a != b)
			t.addedge(a, b);
	}
	t.run();
	cout << size(t.comps) << '\n';
	reverse(all(t.comps));
	for (auto &&v : t.comps) {
		cout << size(v);
		for (auto i : v)
			cout << ' ' << i;
		cout << '\n';
	}
}