Tarjan算法求联通分量

Tarjan算法之所以这么出名，我的理解是他的复杂度很低，而且可以一遍DFS跑出结果。
关于tarjan算法的讲解可以参考以下三篇Blog：

1. https://www.luogu.org/blog/styx-ferryman/chu-tan-tarjan-suan-fa-qiu-qiang-lian-tong-fen-liang-post
2. https://blog.****.net/qq_34374664/article/details/77488976
3. https://www.cnblogs.com/shadowland/p/5872257.html

这里写了一道CSP的题目：

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

const int maxn = 1e5 + 5;
struct Edge { int to, next; }edges[maxn];
int head[maxn], dfn[maxn], low[maxn], instack[maxn];
int n, m, u, v, tot, time, cnt; stack<int> S;

void add(int u, int v) {
	edges[tot] = { v,head[u] };
	head[u] = tot++;
}

void tarjan(int s) {
	dfn[s] = low[s] = ++time;  //dfn[i]：结点i的到访时间，low[i]：结点i能到的最早的父节点
	S.push(s); instack[s] = 1; //入栈并记录状态
	for (int e = head[s]; e != -1; e = edges[e].next) {
		int v = edges[e].to;
		if (!dfn[v]) {	//如果当前点未访问，
			tarjan(v);	//那么tarjan深度遍历.
			low[s] = min(low[s], low[v]); //v点遍历结束，更新v的父节点s的low[s], 也许v及后续可达更早祖先
		}
		else if (instack[v])
			low[s] = min(low[s], dfn[v]); //v点已经在栈中，那么更新当前点的low[s], 在栈中的点先访问是祖先
	}
	if (dfn[s] == low[s]) { //某个结点dfn[s] == low[s]，那么他是一个连通分量的根，那么栈中元素可以pop
		int sum = 0;
		while (1) {
			int top = S.top();
			instack[top] = 0;
			S.pop();
			sum++;
			if (top == s) 
				break;
		}
		if (sum > 1) 
			cnt += sum*(sum - 1) / 2;
	}
}

int main(){
	memset(head, -1, sizeof(head));
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		scanf("%d%d", &u, &v);
		add(u, v);
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) tarjan(i);
	printf("%d\n", cnt);
	return 0;
}