模板
// Problem: P2863 [USACO06JAN] The Cow Prom S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2863
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)#include <cstdio> // 用于输入输出函数，如scanf、printf
#include <cstring> // 用于内存操作函数，如memset
#include <algorithm> // 用于算法函数，如min
using namespace std; // 引入标准命名空间，避免使用std::前缀// 定义常量：N为最大节点数，M为最大边数
const int N = 1e4 + 10, M = 1e5 + 10;int n, m; // n表示节点数，m表示边数// 邻接表存储图：
// e[]存储边的终点，ne[]存储下一条边的索引，h[]存储表头（每个节点的第一条边索引）
// idx用于记录边的数量，作为边的唯一标识
int e[M], ne[M], h[N], idx;// Tarjan算法相关变量：
// dfn[]存储节点的深度优先搜索次序（时间戳）
// low[]存储节点能回溯到的最早时间戳
// timestamp用于记录时间戳
int dfn[N], low[N], timestamp;// 栈相关变量：
// stk[]用于存储当前路径上的节点
// top为栈顶指针
// instk[]标记节点是否在栈中
int stk[N], top;
bool instk[N];// 强连通分量(SCC)相关变量：
// scc[]存储每个节点所属的强连通分量编号
// size[]存储每个强连通分量的大小
// cnt为强连通分量的数量
int scc[N], size[N], cnt;// 向图中添加一条从a到b的有向边
// a: 起点, b: 终点
void add(int a, int b) {e[idx] = b; // 存储边的终点ne[idx] = h[a]; // 将新边的下一条边指向当前a的第一条边h[a] = idx++; // 更新a的第一条边为当前边，边计数加1
}// Tarjan算法核心函数，用于寻找强连通分量
// u: 当前处理的节点
void tarjan(int u) {// 初始化当前节点的dfn和low值为当前时间戳，并将时间戳加1dfn[u] = low[u] = ++timestamp;// 将当前节点入栈，并标记为在栈中stk[++top] = u;instk[u] = true;// 遍历当前节点的所有邻接边for (int i = h[u]; ~i; i = ne[i]) { // ~i 等价于 i != -1int v = e[i]; // 获取边的终点vif (!dfn[v]) { // 如果v未被访问过tarjan(v); // 递归处理v// 更新当前节点的low值为其自身low值与v的low值的最小值low[u] = min(low[u], low[v]);} // 如果v已被访问且在栈中，说明形成环，更新当前节点的low值else if (instk[v]) {low[u] = min(low[u], dfn[v]);}}// 当节点u的dfn值等于low值时，说明u是一个强连通分量的根if (dfn[u] == low[u]) {cnt++; // 强连通分量数量加1int v; // 用于临时存储出栈的节点// 将栈中从u开始的所有节点弹出，这些节点构成一个强连通分量do {v = stk[top--]; // 栈顶节点出栈instk[v] = false; // 标记为不在栈中scc[v] = cnt; // 记录v所属的强连通分量编号size[cnt]++; // 该强连通分量的大小加1} while (v != u); // 直到弹出的节点是u为止}
}int main() {// 读取节点数和边数scanf("%d%d", &n, &m);// 初始化邻接表头为-1（表示无邻接边）memset(h, -1, sizeof h);// 读取m条边并添加到图中for (int i = 1, a, b; i <= m; i++) {scanf("%d%d", &a, &b); // 读取边的起点a和终点badd(a, b); // 添加边}// 对所有未访问的节点执行Tarjan算法for (int i = 1; i <= n; i++) {if (!dfn[i]) { // 如果节点i未被访问tarjan(i); // 处理节点i}}// 统计大小大于1的强连通分量的数量int ans = 0;for (int i = 1; i <= cnt; i++) {if (size[i] > 1) { // 如果强连通分量i的大小大于1ans++; // 计数加1}}// 输出结果printf("%d\n", ans);return 0;
}