Tarjan 强连通分量 板子

#include <bits/stdc++.h>

using namespace std;

const int N = 10005;
int n, m;
int scc[N], siz[N], cnt;
int dfn[N], low[N], tot;
bitset<N>instk;
stack<int>stk;
vector<int>e[N];
vector<int>ans[N];

void tarjan(int u)
{
	dfn[u] = low[u] = ++tot;
	stk.push(u);
	instk[u] = 1;
	
	for (int v : e[u]) {
		if (!dfn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		} else if (instk[v]) {
			low[u] = min(low[u], dfn[v]);
		}
	}
	if (dfn[u] == low[u]) {
		// scc root
		cnt++;
		int v;
		do {
			v = stk.top(); stk.pop();
			instk[v] = 0;
			ans[u].push_back(v);
		} while (v != u);
		if (ans[u].size() == 1) {
		    cnt--;
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	for (int i = 1, a, b; i <= m; i++) {
		scanf("%d%d", &a, &b);
		e[a].push_back(b);
	}
	for (int vert = 1; vert <= n; vert++) {
		if (!dfn[vert]) {
			tarjan(vert);
		}
	}
// 	for (int i = 1; i <= n; i++) {
// 		sort(ans[i].begin(), ans[i].end());
// 	}
	printf("%d\n", cnt);
// 	for (int i = 1; i <= n; i++) {
// 		if (!ans[i].size()) continue;
// 		for (int j = 0; j < ans[i].size(); j++) {
// 			printf("%d ", ans[i][j]);
// 		}
// 		printf("\n");
// 	}
	return 0;
}