tarjan强连通分量

dfs维护两个数组
一个是dfs序，另一个是$u$的子树中能够回溯到的最早的已经在栈中的节点

剩下的可以考虑看【341 强连通分量 Tarjan 算法】 https://www.bilibili.com/video/BV1SY411M7Tv/?share_source=copy_web&vd_source=83c006dc7cb8936b245d101a58d9aa32

至于low[u] = min(low[u], dfsn[v]);能不能替换为low[u] = min(low[u], low[v]);
视频里的答案是可以，但是为了和其他代码统一，建议不换
而其他网站说不可以，例如wiki和geeksforgeeks

#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

const int N = 1e4 + 5;

vector<int> edge[N];
int dfsn[N], tot;//dfs序
int low[N];
stack<int> s;
bool in_stack[N];//是否在栈里
int scc[N], sc;//节点i所在scc编号
int sz[N];//强连通分量i的大小

void tarjan(int u) {
	low[u] = dfsn[u] = ++tot;
	s.push(u);
	in_stack[u] = true;
	for (int i = 0; i < edge[u].size(); ++i) {
		int v = edge[u][i];
		if (!dfsn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stack[v]) {
			low[u] = min(low[u], dfsn[v]);
		}
	}
	if (dfsn[u] == low[u]) {
		++sc;
		while (s.top() != u) {
			scc[s.top()] = sc;
			++sz[sc];
			in_stack[s.top()] = false;
			s.pop();
		}
		scc[u] = sc;
		++sz[sc];
		in_stack[u] = false;
		s.pop();
	}
}

int main() {
	int n, m, a, b, ans = 0;
	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d", &a, &b);
		edge[a].push_back(b);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfsn[i]) {
			tarjan(i);
		}
	}

	return 0;
}

洛谷P2863

#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;

const int N = 1e4 + 5;

vector<int> edge[N];
int dfsn[N], tot;//dfs序
int low[N];
stack<int> s;
bool in_stack[N];//是否在栈里
int scc[N], sc;//节点i所在scc编号
int sz[N];//强连通分量i的大小

void tarjan(int u) {
	low[u] = dfsn[u] = ++tot;
	s.push(u);
	in_stack[u] = true;
	for (int i = 0; i < edge[u].size(); ++i) {
		int v = edge[u][i];
		if (!dfsn[v]) {
			tarjan(v);
			low[u] = min(low[u], low[v]);
		}
		else if (in_stack[v]) {
			low[u] = min(low[u], dfsn[v]);
		}
	}
	if (dfsn[u] == low[u]) {
		++sc;
		while (s.top() != u) {
			scc[s.top()] = sc;
			++sz[sc];
			in_stack[s.top()] = false;
			s.pop();
		}
		scc[u] = sc;
		++sz[sc];
		in_stack[u] = false;
		s.pop();
	}
}

int main() {
	int n, m, a, b, ans = 0;
	scanf("%d%d", &n, &m);
	while (m--) {
		scanf("%d%d", &a, &b);
		edge[a].push_back(b);
	}
	for (int i = 1; i <= n; ++i) {
		if (!dfsn[i]) {
			tarjan(i);
		}
	}
	for (int i = 1; i <= sc; ++i) {
		if (sz[i] > 1)++ans;
	}
	printf("%d\n", ans);
	return 0;
}