图论部分
\(\text{I}\). 连通性部分
有向图强连通分量 \(\text{(SCC)}\)
代码模板
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, m, num, scc_cnt, top;
bool instk[N];
int dfn[N], low[N], stk[N], blg[N];
vector<int> g[N], ans_scc[N], new_g[N];
inline int read(){
int s = 0, w = 1;
char ch = getchar();
while(!isdigit(ch)) { w = (ch == '-' ? -1 : 1); ch = getchar(); }
while(isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
return s * w;
}
inline void write(int x){
if(x < 0) { x = -x, putchar('-'); }
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
void scc(int u){
dfn[u] = low[u] = ++num;
stk[++top] = u, instk[u] = true;
for(int v : g[u]){
if(!dfn[v]){
scc(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_cnt++;
int t;
do{
t = stk[top--];
instk[t] = false;
ans_scc[scc_cnt].push_back(t), blg[t] = scc_cnt;
}while(t != u);
}
}
int main(){
n = read(), m = read();
while(m--){
int u = read(), v = read();
if(u != v)
g[u].push_back(v);
}
for(int i = 1; i <= n; i++)
if(!dfn[i])
scc(i);
// 输出每个 SCC 的元素
for(int i = 1; i <= scc_cnt; i++){
printf("SCC #%d : %d elements : ", i, ans_scc[i].size());
sort(ans_scc[i].begin(), ans_scc[i].end());
for(int u : ans_scc[i])
printf("%d ", u);
printf("\n");
}
// 缩点
for(int i = 1; i <= n; i++)
for(int j : g[i])
if(blg[i] != blg[j])
new_g[blg[i]].push_back(blg[j]);
// 输出缩点之后的新图
printf("New graph :\n");
for(int i = 1; i <= scc_cnt; i++)
for(int j : new_g[i])
printf("SCC #%d -> SCC #%d\n", i, j);
return 0;
}
注意：
- 在判断一条边是不是 B 边或有用的 C 边时，需要判断这条边指向的点是否在栈中。
- 在求出 SCC 之后，清理栈的时候
while循环至少需要执行一次，这也是使用do...while循环的原因。 - 在求出 SCC 之后，清理栈的时候要把
instk[t]重置成false，代表栈顶的top也要减一。但注意，应该先取栈顶元素再自减，也就是后自减，这与前文入栈时用的是先自增再入栈（即前加）有关。因为这导致了top指向的元素就是栈顶，而不是栈顶元素 $ + 1$。 - 缩点的时候如果要处理 SCC 之间的连边，需要先判断这条边的两个端点是不是不在一个 SCC 中。这是因为一个 SCC 内部的连边不是几个 SCC 之间的连边。
- SCC 只适用于有向图。如果是无向图，那么与 SCC 定义类似的是 EDCC 和 VDCC。