CF1559D2 Mocha and Diana(并查集&思维) 题解

发布于 2021-08-23  63 次阅读


LaTeX炸了看这里

题目大意

给定给定两张分别有 $n$ 个点 $m_1$ 条边,$n$ 个点 $m_2$ 条边的无向图 $A,B$。

现在你有一种操作,可以在两张图中同时加入 $(x,y)$ 这条边。

要求在每次操作后仍然满足两张图都是森林。求最多能加多少边,并输出一种合法方案。

$n,m_1,m_2 \le 10^5$。

解题思路

神仙思维题,方法太妙了。

这道题是 CF1559D1 的困难版,简单版的数据范围为 $n,m_1,m_2 \le 10^3$。

在简单版中,我们发现:

  1. 能加入 $(x,y)$ 当且仅当 $x,y$ 在两张图中都属于同一个连通块。
  2. 加入边的顺序是不会影响结果的。

对于后者的口胡证明:考虑一个最终状态,如果两个图的连通块个数均大于 1,那么我们设 $A$ 图中连通块大小分别为 $a,n-a$,$B$ 中连通块大小分别为 $b,n-b$,并且方便起见,我们设 $a,b \le \lfloor \frac{n}{2} \rfloor$ 并且 $a \le b$,那么对于一个 $a$ 中的点 $x$,如果 $x$ 在 $B$ 图的 $b$ 中,那么一定不能与 $a$ 连线的点的个数至多为 $a-1+b-1=a+b-2<n$。如果 $x$ 在 $B$ 图的 $n-b$ 中,一定不能与 $a$ 连线的个数至多为 $a-1+(n-b-1)=n+a-b-2<n$。于是一定可以找到一个点可以与 $a$ 连线。而当有一个图的连通块个数等于 1 时,一定不能再找到连线。

由此可以发现,只要最后是一个连通块,其实合并的过程是无所谓的,加边的条数是固定的

可能有点不严谨,以感性理解为主。

那么考虑如何优化这个东西。官方题解是使用 std::set 来维护,时间复杂度 $O(n \log^2 n)$,不想写诶。

那怎么办呢?我们考虑优化这个过程,从过程中挖掘性质。

我们先确定一个点 $x$,然后先进行一波连边。

我们考虑此时连边后的这个图具有什么性质:每个点不可能两个图中都不与 $x$ 连通。

那么我们设 $A$ 中不与 $x$ 连通的点集为 $sta1$,$B$ 中不与 $x$ 连通的点集为 $sta2$。

那么由上面的性质得 $sta1$ 与 $sta2$ 的交集为空集。

我们在这两个集合里面各任取一个点 $a,b$,则 $a$ 在 $A$ 中与 $x$ 在同一连通块,$b$ 在 $B$ 中与 $x$ 不在同一连通块,那么也即 $a$ 与 $b$ 不在同一连通块。在 $B$ 图中也是同理。那么即 $a$ 与 $b$ 可以连边。

所以在 $sta1$,$sta2$ 中,我们任意各取两个点都是可以连边的,总共有 $\min{|sta1|,|sta2|}$ 条边,容易发现这就是最大的答案(剩下的点显然不可能再连边了)。

Code

采用 struct 实现 $A,B$ 两图中的并查集,代码应该会优美一点。

#include<bits/stdc++.h>
using namespace std;
const int N=500005;

int n,m1,m2;
bool used[N];
vector <int> sta1,sta2;
vector < pair <int,int> > ans;

struct DSU{
    int fa[N];

    inline void Init(){ for (int i=1;i<=n;++i) fa[i]=i; }

    inline int getfa(int x){
        if (fa[x]==x) return x;
        else fa[x]=getfa(fa[x]);
        return fa[x];
    }

    inline bool Merge(int x,int y){
        int fx=getfa(x),fy=getfa(y);
        if (fx==fy) return false;
        fa[fx]=fy;
        return true;
    }

    inline bool Query(int x,int y){
        return getfa(x)!=getfa(y);
    }
}s1,s2;

inline int read(){
    int x=0,f=1; char ch=getchar();
    while (!isdigit(ch)){ if (ch=='-') f=-1; ch=getchar(); }
    while (isdigit(ch)){ x=x*10+ch-'0'; ch=getchar(); }
    return x*f;
}

int main(){
    //freopen("CF1559D2.in","r",stdin);
    //freopen("CF1559D2.out","w",stdout);
    n=read(),m1=read(),m2=read();
    s1.Init(),s2.Init();
    for (int i=1;i<=m1;++i){
        int x=read(),y=read();
        s1.Merge(x,y);
    }
    for (int i=1;i<=m2;++i){
        int x=read(),y=read();
        s2.Merge(x,y);
    }
    for (int i=2;i<=n;++i)
        if ((s1.Query(1,i)) && (s2.Query(1,i))){
            s1.Merge(1,i),s2.Merge(1,i);
            ans.push_back(make_pair(1,i));
            used[i]=true;
        }
    for (int i=2;i<=n;++i){
        if (used[i]) continue;
        if (s1.Query(1,i)){ sta1.push_back(i); s1.Merge(1,i); }
        else if (s2.Query(1,i)){ sta2.push_back(i); s2.Merge(1,i); }
    }
    for (int i=0;i<min(sta1.size(),sta2.size());++i)
        ans.push_back(make_pair(sta1[i],sta2[i]));
    printf("%d\n",ans.size());
    for (int i=0;i<ans.size();++i)
        printf("%d %d\n",ans[i].first,ans[i].second);
    return 0;
}

我们无法选择过去,但我们可以改变未来。