一、最近公共祖先（LCA）
LCA：Least Common Ancestor
P3379 【模板】最近公共祖先（LCA）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickin(void)
{
ll ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
// 存查询的数据结构
typedef pair<int, int> P; // first -- 另一个节点; second -- 查询编号
const int MAX = 5e5 + 3;
int N, M, S; // N -- 节点数; M -- 查询数; S -- 根节点
vector<int> G[MAX]; // 存树，按无向图存储
vector<P> query[MAX]; // 存查询，双向存
int par[MAX], ans[MAX]; // par[] -- 各节点的父节点; ans[] -- 查询答案，按编号存储
bool vis[MAX]; // vis[] -- 是否访问该节点
// 并查集初始化
void init(void)
{
for (int i = 1; i <= N; ++i)
par[i] = i;
}
// 并查集查询
int find(int x)
{
if (par[x] == x) return x;
else
return par[x] = find(par[x]);
}
// tarjan算法 + 并查集
void tarjan(int u)
{
vis[u] = true; // 入u, 标记u
// 遍历u的每条边
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!vis[v]) // 防止访问父节点
{
tarjan(v);
par[v] = u; // 回u, v指向u
}
}
// 离u, 处理查询
for (int i = 0; i < query[u].size(); ++i)
{
P p = query[u][i];
int v = p.first, id = p.second;
if (vis[v]) ans[id] = find(v); // 若v被访问过，则v的根节点即所求
}
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
N = quickin(), M = quickin(), S = quickin();
for (int i = 0; i < N - 1; ++i)
{
int a, b;
a = quickin(), b = quickin();
G[a].push_back(b); // 双向存边
G[b].push_back(a);
}
for (int i = 0; i < M; ++i)
{
int a, b;
a = quickin(), b = quickin();
query[a].push_back(P(b, i)); // 双向存查询; i -- 查询编号
query[b].push_back(P(a, i));
}
init();
tarjan(S);
for (int i = 0; i < M; ++i)
cout << ans[i] << endl;
return 0;
}
二、强连通分量（SCC）
SCC：Strongly Connected Component
B3609 [图论与代数结构 701] 强连通分量
1、基本概念
搜索树:对图深搜时，每个节点仅访问一次，节点按被访问的顺序和访问时经过的有向边组成搜索树。
有向边的分类：
- 树边：搜索树中的边
- 返祖边：指向祖先节点的边
- 横插边：右子树指向左子树的边
- 前向边：指向子孙节点的边
定理1：返祖边与树边必定构成环，横插边可能与树边构成环，前向边无用。
定理2：强连通分量以树的形式存在于搜索树中，每个强连通分量都有一个根，其余节点都在根的子树中。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll quickin(void)
{
ll ret = 0;
bool flag = false;
char ch = getchar();
while (ch < '0' || ch > '9')
{
if (ch == '-') flag = true;
ch = getchar();
}
while (ch >= '0' && ch <= '9' && ch != EOF)
{
ret = ret * 10 + ch - '0';
ch = getchar();
}
if (flag) ret = -ret;
return ret;
}
const int MAX = 1e4 + 3;
int N, M; // N -- 节点数; M -- 边数
vector<int> G[MAX]; // 存有向图
int dfn[MAX], low[MAX], tot;
/*
dfn[] -- 时间戳，各节点第一次被访问的顺序（也可以起到vis[]的作用）
low[] -- 从该节点出发，能访问到的最早的时间戳
tot -- 更新时间戳
*/
stack<int> S; // 将节点按时间戳压栈
bool instk[MAX]; // 该节点是否在栈中
vector<vector<int>> ans; // 存储强连通分量
void tarjan(int u)
{
// 入u，盖戳，入栈
dfn[u] = low[u] = ++tot;
S.push(u), instk[u] = true;
// 遍历u的每条边
for (int i = 0; i < G[u].size(); ++i)
{
int v = G[u][i];
if (!dfn[v]) // 未访问过v（在搜索树中，v是u的孩子）
{
tarjan(v);
low[u] = min(low[u], low[v]); // 回u，更新low
}
else if (instk[v]) // 访问过v，且在栈中（在搜索树中，v是u的祖先）
{
low[u] = min(low[u], dfn[v]);
}
}
// 离u，处理强连通分量
if (dfn[u] == low[u])
{
vector<int> scc;
int t;
do
{
t = S.top();
S.pop(), instk[t] = false;
scc.push_back(t);
} while (t != u);
sort(scc.begin(), scc.end());
ans.push_back(scc);
}
}
bool cmp(const vector<int> &a, const vector<int> &b)
{
return a[0] < b[0];
}
int main()
{
#ifdef LOCAL
freopen("test.in", "r", stdin);
#endif
N = quickin(), M = quickin();
for (int i = 0; i < M; ++i)
{
int a, b;
a = quickin(), b = quickin();
G[a].push_back(b); // 存储有向边
}
// 图未必是连通的
for (int i = 1; i <= N; ++i)
{
if (!dfn[i])
tarjan(i);
}
sort(ans.begin(), ans.end(), cmp);
cout << ans.size() << endl;
for (int i = 0; i < ans.size(); ++i)
{
for (int j = 0; j < ans[i].size(); ++j)
{
cout << ans[i][j] << ' ';
}
cout << endl;
}
return 0;
}
