题解：P11954 「ZHQOI R1」删边

· · 题解

题目传送门

分析

刚开始还以为是割边板子题，但又注意到要满足：

删完后图中没有孤立点（即度数为 0 的点）

而且可以删去多条边，所以答案和割边属于是既不充分也不必要，一个显然的想法是找出原图中的任意一棵生成树，然后一次树上 DFS 找到可以用来断开的边。因为树少一条边肯定可以使得图不连通，而只需要找到一条边使得两端点对应的联通块均不为 1 即可，最后如果找不到就直接输出 -1 即可。

看上去挺对，我考场上也的确这么写的就成功 A 掉（还因为第一次A这么快签到题而沾沾自喜），但是赛又后仔细想想发现这个代码很好 hack，也就是说数据水了。

我们先想一下是不是所有的树都一定找得到合法的边？肯定不是，不然这题为啥有无解的测试点。那么什么样的树无解呢？假设这棵树有 n 个节点， 我们可以这么考虑，无解就意味着每条边的两端点在断开这条边之后，至少存在一个所包含的连通块只含自己，换句话说有一个点在这棵树上只连了一条边。而所有这 n-1 条边都要满足这样的性质，那么至少需要 n-1 个点只连了一条边（有点类似抽屉原理），那只可能是菊花图了。

所以我们之前的想法可能出 BUG 的图就是菊花图添加若干条边，如果程序恰好跑出来的生成树是菊花图（这个概率挺低的，所以假代码可以通过），那么就会误判无解的情况。

不过对于这样子的图应该怎么解决呢？首先如果图本身就是菊花图，我们的程序会正确报告无解，不会出问题。而题目中的“简单无向连通图”告诉我们这个图没有重边和自环，那么新添加的边就只会是菊花图的叶子节点之间的连边（如果把所有点连向的那个点定为根），那么我们就一定可以找到一个生成树不是菊花图。

具体地，我们只需要从根出发遍历这个图找到生成树即可，正确性很好证明，因为根到达一个节点后会访问其所有出边，如果此时某个叶子节点存在与另一叶子节点的连边，那么就会在遍历根节点与这个节点的直接边之前访问到这个点，成功使得这个节点所连接的边增加，使得求解出的生成图不再是一棵菊花图，正确的找到答案！

代码实现

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
const int N=5e5+10;
int n,m,u,v,dfn[N],num,siz[N];
int head[N],cnt=1,rt=1,du[N];
bool vis[N<<1],vv[N<<1],ok;
vector<PII> ans;

struct node{
    int nxt,to;
}edge[N<<1];

void add(int from,int to)
{
    du[to]++;
    edge[++cnt].nxt=head[from];
    edge[cnt].to=to;
    head[from]=cnt;
}

void dfs(int u)
{
    dfn[u]=++num;
    for(int e=head[u];e;e=edge[e].nxt)
    {
        int v=edge[e].to;
        if(dfn[v]) continue;
        vis[e]=vis[e^1]=1;dfs(v);
    }
}

void dfs0(int u,int fa)
{
    siz[u]=1;
    for(int e=head[u];e;e=edge[e].nxt)
    {
        if(ok) return;
        int v=edge[e].to;
        if(v==fa||!vis[e]) continue;
        dfs0(v,u);siz[u]+=siz[v];
        if(!ok&&siz[v]>1&&n-siz[v]>1)//端开u，v之后图会被分为v的子树和不含v子树的其他部分的两个连通块
        {
            ok=1;ans.push_back(make_pair(u,v));
            return;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&m);
    while(m--) scanf("%d%d",&u,&v),add(u,v),add(v,u);
    for(int i=1;i<=n;i++) if(du[i]==n-1) rt=i;//把这行删去会被下面的数据hack，误判无解
    dfs(rt);//先求解生成树，生成树上的边用vis来标记
    for(int i=1;i<=n;i++)
        for(int e=head[i];e;e=edge[e].nxt)
            if(!vis[e]&&!vv[e]) vv[e]=vv[e^1]=1,ans.push_back(make_pair(i,edge[e].to));//使用成对变换技巧vv数组为true表示已经输出过了就不重复输出
    dfs0(rt,0);//找合法的点
    if(!ok)//无解
    {
        printf("-1\n");
        return 0;
    }
    printf("%d\n",(int)ans.size());
    for(auto i:ans) printf("%d %d\n",i.first,i.second);
    return 0;
}

最后贴一下 hack，顺便说一下构造的原理是什么（希望管理可以把这组 hack 或者类似更强的数据加到测试点里面去，防止有人和我一样的错误想法却通过了本题）

6 6
1 5
1 2
2 3
2 4
2 5
2 6

这是一棵以 2 根的菊花图添了 1 5 这条边形成的图，要让这个 hack 起作用要满足两点：

  1. 用链式前向星存图（邻接表），保证了先读入的边后遍历。
  2. 以根为 1 遍历整个图，这样子从 1 出发会先遍历到根节点 2，从而所遍历到的生成树就是菊花图，导致误判了无解。

其实可能很多人的习惯也是上面的两个，所以如果有人和我有类似想法的可能会被 hack 到。不过可能会有人觉得这样子的 hack 很好破解，根本没啥用，使用 vector 存图或者随机选一个点为根都可以不被 hack，但是心存侥幸总是不好的，如果出题人为了卡错解完全可以整成多组数据，一部分用来卡错解。比如有 10^5 组，然后每组数据的 n 都很小，把所有可能的 2^{\frac{n(n-1)}{2}} 种图都添加进去，让所有错解都不可能通过。

通过这道题，我也懂得了许多道理，AC 并不能代表代码正确，只能说大概率正确，我们应该静下心来仔细研究这个算法为什么对？会不会有什么漏洞？能不能做得更好？而不是囫囵吞枣的只追求 AC 率。

最后引用一句《算法竞赛进阶指南》的话与大家共勉：

虽然很多问题的时间复杂度是有下界的，但从某种程度上说，算法的设计、优化是永无止境的。读者不应被已有的思维束缚，或只满足于得到 AC，而是应该尽可能地挖掘、总结一个模型的相关性质，探究其本质。