画图制胜!!!
Statement
给定一个仙人掌图,求至少用多少条简单路径或者简单环可以恰好覆盖所有边
\(n\le 10^5\)
Solution
主要参考了 https://www.cnblogs.com/pealfrog/p/15228596.html
有这样三种简单环:
第一种我们显然只需要用一个简单环覆盖就好了,第二种我们无论如何需要使用两条,第三种我们也需要两条
我们不妨称那些环外边的数量为 环的度数
我们还可以像这样来理解:
第二种,我们在覆盖那条环外边的时候顺便覆盖了环内的一些边,但可惜此时还差一条边
第三种,我们可以在覆盖两条环外边的时候顺手就把整个环给覆盖掉,所以可以认为是说这个环不存在贡献了,这个环被我们删掉了
也就是说,只要一个环的度数 \(\ge 2\) ,那么它就可以被删除
在度数为 \(0/1\) 的时候,需要额外的一费
现在我们假装把所有环都干掉了,变成了一个无向无环图
考虑这样几种情况:
考虑每个点的贡献,即为了覆盖于这个点有关联的边所付出费用
图一中,每个点贡献 \(1\) ,一条边两个端点,除 \(2\)
图二中,度数为 \(2\) 的点贡献为 \(0\)
图三中,每个点贡献 \(1\) ,可以看做隔离左侧三个点,先做一次图二操作,把左上点和下点缩到了中心点上,然后变成了图一情况,此时中心点有贡献 \(1\)。一条边两个端点,除 \(2\)。
图四中,中心点无贡献
我们于是得到这样的一个规律:
偶度数点贡献 \(0\) ,奇度数点贡献 \(1\),最后将总贡献除 \(2\) 即可
我们可以使用 tarjan 找环(边双),所以它是 \(O(n)\) 的???
#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;
int read(){
int s=0,w=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
return s*w;
}
struct Edge{
int nex,to;
}edge[N<<1];
int head[N],dfn[N],low[N],deg[N];
bool vis[N],bd[N<<1];
vector<int>cir[N];
int n,m,elen=1,tim,cnt,ans;//
void addedge(int u,int v){
edge[++elen]={head[u],v},head[u]=elen;
edge[++elen]={head[v],u},head[v]=elen;
deg[u]++,deg[v]++;
}
void tarjan(int u,int fath){
dfn[u]=low[u]=++tim;
for(int e=head[u],v;v=edge[e].to,e;e=edge[e].nex)
if(!dfn[v]){
tarjan(v,u),low[u]=min(low[u],low[v]);
if(low[v]>dfn[u])bd[e]=bd[e^1]=true;
}else if(v^fath)low[u]=min(low[u],dfn[v]);
}
void dfs(int u){
vis[u]=true,cir[cnt].push_back(u);
for(int e=head[u],v;v=edge[e].to,e;e=edge[e].nex)
if(!bd[e]&&!vis[v])dfs(v);
}
signed main(){
n=read(),m=read();
for(int i=1,u,v;i<=m;++i)
u=read(),v=read(),addedge(u,v);
if(!m)return puts("0 0"),0;
for(int i=1;i<=n;++i)tarjan(i,0);
for(int i=1;i<=n;++i)if(!vis[i])cnt++,dfs(i);
if(cnt==1)return printf("1 %d\n",m),0;
for(int i=1;i<=n;++i)ans+=deg[i]&1;
ans>>=1;
for(int i=1,t;t=0,i<=cnt;++i)
if(cir[i].size()!=1){
for(int j=0;j<(int)cir[i].size();++j)
t+=deg[cir[i][j]]>=3;
ans+=t<=1;
}
printf("%d %d\n",ans,m);
return 0;
}