违规用户名690561 @ 2024-10-19 11:20:38
我仿照题解2写的
#include<bits/stdc++.h>
using namespace std;
int n, m, s1, s2;
int dfn[2000005], low[2000005], tot, len;
vector<pair<int, int>> e[2000005];
vector<int> v;
vector<vector<int>> ans;
stack<int> st;
void tarjan(int u, int las) {
dfn[u] = low[u] = ++tot;
st.push(u);
for(auto i : e[u]) {
int v = i.first;
if(i.second == (las ^ 1)) {
continue;
}
if(dfn[v] == 0) {
tarjan(v, i.second);
low[u] = min(low[u], low[v]);
} else {
low[u] = min(low[u], dfn[v]);
}
}
if(dfn[u] == low[u]){
v.clear();
v.push_back(u);
while(st.top() != u){
v.push_back(st.top());
st.pop();
}
st.pop();
ans.push_back(v);
}
return;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 1; i <= m; i++) {
scanf("%d %d", &s1, &s2);
e[s1].push_back({s2, i << 1});
e[s2].push_back({s1, i << 1 | 1});
}
for(int i = 1; i <= n; i++) {
if(!dfn[i]) {
tarjan(i, 0);
}
}
printf("%d\n", (int)ans.size());
for(auto i : ans){
printf("%d ", (int)i.size());
for(auto j : i){
printf("%d ", j);
}
printf("\n");
}
return 0;
}
一个疑问:为什么tarjan函数写得如此简单(甚至比别的tarjan算法都简单)就能求出边双?
by Melo_DDD @ 2024-10-19 11:29:34
@tzxxzt 建议学习 tarjan 算法
by 违规用户名690561 @ 2024-10-19 11:54:35
@Melo_DDD 。。。