DTOJ #5089 沙漠点列

DTOJ #5089 沙漠点列

题面

我们称一张无向图是仙人掌，当且仅当这张无向图连通且每条边最多属于一个简单环。我们称一张无向图是沙漠，当且仅当这张无向图中所有连通子图都是仙人掌。

给出一个 n个点，m 条边的沙漠，你可以删去其中的 k 条边。求能分成的连通块数量最大值。

数据范围

3 ≤ n ≤ 1 0 6 , 0 ≤ k ≤ m ≤ 2 × 1 0 6 , 1 ≤ u , v ≤ n 3 leq n leq 10^6,0 leq k leq m leq 2 times10^6,1 leq u,v leq n 3≤n≤106,0≤k≤m≤2×106,1≤u,v≤n

题解

显然，由于沙漠的性质，一条边最多属于一条环。
整个图上的边就分为了两种：
1. 1. 1.环上的边
2. 2. 2.非环上的边
接着我们考虑一下断边的情况：
对于环上的边，如果把它断开，当前这块连通块并不能分为2个联通块，因为环断开就变成链了，它还是联通的。得接着断才能把它断成不连通。
对于非环上的边，如果把它断开，当前这块连通块就变成2个连通块了。

于是，基于贪心的思想，我们优先选择断非环边（因为只要断i次就能多i个连通块）断完之后，若k仍有剩余，此时的图一定是若干个环。

思考一下：当我们如果把一个长度为 n n n的环断开了，它就会变成长度为 n n n的链，即有 n n n条非环边。然后就又回到第一种情况。

所以，对于有若干个长度不同的环，我们想要尽可能的通过断开一个环，使得它出现的非环边最大。（断开一个环的代价都是1），这样我们k的消耗就能尽可能的小。

注意事项

判断非环边和环边用dfs即可，记录一下时间戳 d e p i dep_i depi​（即dfs序），然后判断对于一个节点 i i i是否有与 j j j相连，并且 0 < d e p j 0 < dep_j 0<depj​然后回溯回去即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
inline int read(){int k=0,f=1;char ch;while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9')k=k*10+ch-'0',ch=getchar();return k*f;
}
int n,m,k;
int tot_=1,ver[N*4],fst[N],nxt[N*4],v[N];
int huan[N],d[N],tot,ans,ans_1;
inline void add(int x,int y){ver[++tot_]=y;nxt[tot_]=fst[x];fst[x]=tot_;}
void dfs(int x,int fa,int dep){v[x]=1;d[x]=dep;for(int i=fst[x];i;i=nxt[i]){int y=ver[i];if(y==fa)continue;if(v[y]){if(d[y]<d[x]){huan[++tot]=d[x]-d[y]+1;ans-=huan[tot];}continue;}dfs(y,x,dep+1);}
}
int main(){n=read(),m=read(),k=read();for(int i=1;i<=m;++i){int x=read(),y=read();add(x,y);add(y,x);}ans=m;for(int i=1;i<=n;++i)if(!v[i])dfs(i,0,0),ans_1++;if(k<=ans){printf("%dn",k+ans_1);return 0;}k-=ans;sort(huan+1,huan+tot+1);for(int i=tot;i>=1;i--){if(k<=huan[i]){ans+=k-1;break;}ans+=huan[i]-1;k-=huan[i];}printf("%dn",ans+ans_1);return 0;
}