求割点
从根节点开始dfs,对于一个顶点u,我们维护三个信息:
- $low_{u}$:不经过父节点能访问的最小时间戳。
- $dfn_{u}$:访问节点的时间戳。
- $father_{u}$:父节点(根节点定义可定义为自身)。
对于一个节点,当且仅当存在一个子节点$v$,有$low_{v}>=dfn_{u}$,即不能通过非父边回到其祖先节点,该点为割点。时间复杂度$O(|V|+|E|)$。
值得注意的是,图不一定联通,要注意处理所有节点。
参考代码:
//luogu P3388
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
int n, m;
int ind, ans;
int low[N], dfn[N];
bool vis[N], flag[N];
vector<int> E[N];
int min(int a, int b) {
return a < b ? a : b;
}
void tarjan(int u, int father) {
vis[u] = true;
low[u] = dfn[u] = ++ind;
int child = 0;
for ( auto v : E[u] ) {
if ( !vis[v] ) {
++child;
tarjan(v, u);
low[u] = min(low[u], low[v]);
if ( u != father && low[v] >= dfn[u] && !flag[u] ) {
++ans;
flag[u] = true;
}
}
if ( v != father )
low[u] = min(low[u], dfn[v]);
}
if ( father == u && child >= 2 && !flag[u] ) {
flag[u] = true;
++ans;
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
int a, b;
for ( int i = 1; i <= m; ++i ) {
cin >> a >> b;
E[a].push_back(b);
E[b].push_back(a);
}
for ( int i = 1; i <= n; ++i )
if ( !vis[i] ) {
ind = 1;
tarjan(i, i);
}
cout << ans << endl;
for ( int i = 1; i <= n; ++i )
if ( flag[i] )
cout << i << ' ';
return 0;
}
求割边
相较于求割点,求割边只需要将$low_{v}>=dfn_{u}$改为$low_{v}>dfn_{u}$,那么$u,v$之中必存在割边,并且不需要考虑根节点的情况。
参考代码:
//luogu P1656
#include <bits/stdc++.h>
using namespace std;
const int N = 151;
int n, m;
int ind;
int low[N], dfn[N];
set< pair<int, int> > mark;
vector<int> E[N];
int min(int a, int b) {
return a < b ? a : b;
}
void tarjan(int u, int fa) {
low[u] = dfn[u] = ++ind;
for ( auto v : E[u] ) {
if ( !dfn[v] ) {
tarjan(v, u);
if ( dfn[u] < low[v] )
mark.insert({u, v});
low[u] = min(low[u], low[v]);
}
if ( dfn[v] && v != fa )
low[u] = min(low[v], low[u]);
}
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
int a, b;
for ( int i = 1; i <= m; ++i ) {
cin >> a >> b;
E[a].push_back(b);
E[b].push_back(a);
}
tarjan(1, 1);
for ( auto x : mark )
cout << x.first << ' ' << x.second << endl;
return 0;
}