题目链接: 

题目大意：在一个非连通图中，求一个切除图中任意一个割点方案，使得图中连通分量数最大。

解题思路：

一个大陷阱，m可以等于0，这时候要特判，结果就是n-1。

同时出题者脑子秀逗了，也不给C的范围。我开了两倍点大小RE了，于是怒开了五倍点大小才A了。

本题不是连通图，需要先计算原始图中的连通分量。方法就是dfs染色。

然后dfs求割点。

之后枚举割点，由于是非连通图，所以连通分量数=原始分量数+block-1。

-1的原因是，每次相当于对其中一个连通分量计算，加上新的block之后，所以要减-1。

 

#include "cstdio"#include "cstring"#include "vector"using namespace std;#define maxn 10005struct Edge{    int to,next;}e[maxn*5];int dfs_clock,pre[maxn],block,head[maxn],tol;bool cut[maxn],vis[maxn];void addedge(int u,int v){    e[tol].to=v;    e[tol].next=head[u];    head[u]=tol++;}int dfs(int u,int fa){    int lowu=pre[u]=++dfs_clock;    int child=0;    for(int i=head[u];i!=-1;i=e[i].next)    {        int v=e[i].to;        if(!pre[v])        {            int lowv=dfs(v,u);            lowu=min(lowu,lowv);            if(lowv>=pre[u]) cut[u]=true;        }        else if(pre[v]

 

2905876

Accepted

732

2422

2129