割边
在无向图中删了一条边后，图中联通块个数增加，则称该边为割边。
判定
对于一条 \(cur \to i\) 的边，若 \(low_i > dfn_{cur}\)（不能取等，画图便知理由），则该边为割边。
T103481 & P1656
板子。
P1656 code
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,cnt;
struct EDGE{
int v,i;
};
struct NODE{
int u,v,p;
}e[N];
vector<EDGE> G[N];
int dfn[N],low[N];
bool bridge[N];
bool cmp(NODE x,NODE y){
if(x.u!=y.u)
return x.u<y.u;
return x.v<y.v;
}
void tarjan(int cur,int edg){
dfn[cur]=low[cur]=++cnt;
for(auto [v,i]:G[cur]){
if(!dfn[v]){
tarjan(v,i);
low[cur]=min(low[cur],low[v]);
if(low[v]>dfn[cur]){
bridge[i]=1;
}
}
else if (i!=edg) {
low[cur]=min(low[cur],dfn[v]);
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
if(u>v) swap(u,v);
e[i]={u,v,i};
G[u].push_back({v,i});
G[v].push_back({u,i});
}
for (int i=1; i<=n; i++){
if (!dfn[i]) {
tarjan(i,0);
}
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
if(bridge[e[i].p])
cout<<e[i].u<<' '<<e[i].v<<'\n';
return 0;
}
P7687
容易发现只有割边才会成为答案，并且分出的联通块中必须有一个全 A 或全 B，于是直接维护联通块 A 的数量与 B 的数量即可判定。
想到了思路但是认为自己不会写，怎么会是呢。加训 /fn
code
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5,M=1e6+5;
int n,m,k,l,cnt;
struct EDGE{
int u,v;
};
vector<EDGE> ans;
vector<int> G[M];
int dfn[N],low[N];
int siza[N],sizb[N];
void tarjan(int cur,int fa){
dfn[cur]=low[cur]=++cnt;
for(int i:G[cur]){
if(i==fa)
continue;
if(!dfn[i]){
tarjan(i,cur);
low[cur]=min(low[cur],low[i]);
siza[cur]+=siza[i];
sizb[cur]+=sizb[i];
if(low[i]>dfn[cur]&&(!siza[i]||!sizb[i]||siza[i]==k||sizb[i]==l)){
ans.push_back({cur,i});
}
}
else{
low[cur]=min(low[cur],dfn[i]);
}
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>m>>k>>l;
for(int i=1,u;i<=k;i++){
cin>>u;
siza[u]++;
}
for(int i=1,u;i<=l;i++){
cin>>u;
sizb[u]++;
}
for(int i=1,u,v;i<=m;i++){
cin>>u>>v;
G[u].push_back(v);
G[v].push_back(u);
}
tarjan(1,0);
cout<<ans.size()<<'\n';
for(auto i:ans)
cout<<i.u<<' '<<i.v<<'\n';
return 0;
}
CF1761E
妙妙题。tj。
标签：Living,cur,int,dfn,low,sizb,siza,Dream,85 From： https://www.cnblogs.com/XOF-0-0/p/18537054