割边:
`
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+100;
int h[N],e[N*2],ne[N*2],idx;//idx代表每一个节点的序号
//假设有一个节点u,以及其直接相连的若干节点v1,v2,v3
//head[u]代表节点u直接相邻的第一个节点v1的序号(tot1)
//ne[idx1]代表节点u直接相邻的下一个节点的序号(tot2)
//e[idx1]代表序号为idx1的节点的值(v1)
int dfn[N],low[N];
int n,m,num;//num代表每一个节点的时间戳
bool bridge[N*2];//bridge[idx]代表序号为idx的边是否为桥
void add(int a,int b){
e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}
//x代表当前搜索树的根节点,in_edge代表其对应的序号(idx)
void tarjan(int x,int in_edge){
//初始化节点x的时间戳与追溯值
dfn[x] = low[x] = ++num;
for(int i=h[x];i;i=ne[i]){
int y = e[i];//考虑从x出发的每条边(x,y)
//节点y时间戳为0,没有被访问过,即在搜索树上x是y的父节点
if(!dfn[y]){
tarjan(y,i);
low[x] = min(low[x],low[y]);
if(low[y] > dfn[x])
bridge[i] = bridge[i^1] = true;
}
//当前节点被访问过,无向边(x,y)不是搜索树上的边
else if(i != (in_edge^1))
low[x] = min(low[x],dfn[y]);
}
}
int main(){
cin >> n >> m;
idx = 1;//让idx从2开始计数
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
add(x,y),add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) tarjan(i,0);
for(int i=2;i<idx;i+=2)
if(bridge[i]) cout<<e[i^1]<<" "<<e[i];
return 0;
}
`
割点:
判定法则:
若x不是搜索树的根节点(深度优先遍历的起点),则x是割点当且仅当搜索树上存在x的一个子节点y,满足:
dfn[x]<=low[y]
特别的,若x是搜索树的根节点,则x是割点当且仅当搜索树上存在至少两个子节点y1,y2,满足上述条件
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1e5+100;
int h[N],e[N*2],ne[N*2],idx;
int dfn[N],low[N];
int n, m , num, root;
bool cut[N];
void add(int a,int b){
e[++idx] = b,ne[idx] = h[a],h[a] = idx;
}
void tarjan(int x){
dfn[x] = low[x] = ++num;//初始化每个节点的时间戳和追溯值(不放先设追溯值等于时间戳)
int flag = 0;
for(int i=h[x];i;i=ne[i]){//遍历以x为根节点的搜索树
int y = e[i];//考虑从x出发的每条边(x,y)
if(!dfn[y]){ //如果节点y的时间戳为0,即在搜索树上x是y的节点
tarjan(y);//将以x为根的搜索树进行遍历
low[x] = min(low[x],low[y]);//取整个搜索树中最小的low作为x的low
if(low[y] >= dfn[x]){//
flag++;
if(x != root || flag > 1) cut[x] = true;
}
}
//若无向边(x,y)不是搜索树上的边
else low[x] = min(low[x],dfn[y]);
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=m;i++){
int x,y;
cin >> x >> y;
if(x == y) continue;
add(x,y), add(y,x);
}
for(int i=1;i<=n;i++)
if(!dfn[i]) root = i,tarjan(i);//从时间戳为0的点(根节点)遍历
int res = 0;
for(int i=1;i<=n;i++)
if(cut[i]) res++;
cout<<res<<endl;
for(int i=1;i<=n;i++)
if(cut[i]) cout << i <<" ";//如果是割点,就输出
return 0;
}