首先是两篇模板
割边
点击查看代码
int head[N], cnt = 1;
struct Edge{
int from, to, nxt;
}e[N << 1];
void add(int u, int v){
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int dfn[N], back[N], tim, bri_cnt; // dfn[i] 时间戳 back[i] 回退到祖先
bool isbri[N << 1]; // 结果数组
void dfs(int u, int in_edg){ // 和求割点作用相同,相当于传了个 fa
dfn[u] = back[u] = ++tim;
for(int i = head[u]; i != 0; i = e[i].nxt){
int v = e[i].to;
if(!dfn[v]){
dfs(v, i);
back[u] = min(back[u], back[v]);
if(back[v] > dfn[u]){ // >= 变成 > 就是割边了
isbri[i] = isbri[i^1] = true;
bri_cnt++;
}
}
else if(i != (in_edg^1)){ // 这回关系大了,因为判断条件少了等于
back[u] = min(back[u], dfn[v]); // 注意不是 back[v]
}
}
}
边双连通分量
点击查看代码
int head[N], cnt = 1;
struct Edge{
int from, to, nxt;
}e[N << 1];
void add(int u, int v){
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nxt = head[u];
head[u] = cnt;
}
int dfn[N], back[N], tim, bri_cnt, dcc_cnt; // dfn[i] 时间戳 back[i] 回退到祖先
bool isbri[N << 1]; // 结果数组
stack<int> stk;
vector<int> dcc[N];
void dfs(int u, int in_edg){ // 和求割点作用相同,相当于传了个 fa
dfn[u] = back[u] = ++tim;
for(int i = head[u]; i != 0; i = e[i].nxt){
int v = e[i].to;
if(!dfn[v]){
dfs(v, i);
back[u] = min(back[u], back[v]);
if(back[v] > dfn[u]){ // >= 变成 > 就是割边了
isbri[i] = isbri[i^1] = true;
bri_cnt++;
}
}
else if(i != (in_edg^1)){ // 这回关系大了,因为判断条件少了等于
back[u] = min(back[u], dfn[v]); // 注意不是 back[v]
}
}
if(dfn[u] == back[u]){
++dcc_cnt;
while(1){
int y = stk.top(); stk.pop();
dcc[dcc_cnt].push_back(y);
if(y == u) break;
}
}
}