题解：P10350 [PA2024] Modernizacja Bajtocji

· · 题解

这道题目挺巧妙的 。

首先考虑什么情况下不能确定电脑的情况 。

+ 1 2
+ 1 3
+ 2 4
+ 3 5

形如这样的样例是无法确定具体的电脑给了谁 。 明显地 ， 这组样例中人与人的状态连边形成了一棵树 。 同时 ， 我们也能确定这个连通块中有且仅有一个人没有电脑 ， 但是不能确定这个人具体是谁 ， 所以无法确定每个人的状态。

再以此为基础考虑一下什么情况下可以确定每个人都有电脑 。

注意到这句话 ： “电脑被送到了目前还没有电脑的居民手中 。” 所以如果出现了一个环 ， 则一定能确定这个环所在的连通块中每个人都有电脑 。

简单证明一下 ， 如果大小为 n 的连通块中有 n 条边 （ 出现环的充要条件 ）， 这意味着这 n 个人被送了 n 台电脑 ， 且每个人至多有一台电脑 ， 则每个人都有且仅有一台电脑 ， 得证。

再考虑一下电脑损坏的情况。

对于一个树形的连通块 ， 如果某个人的电脑损坏一定意味着他有过电脑 ， 分两种情况讨论一下：

所以我们只用考虑这两种 corner case 即可 。

同时 ， 这个电脑被损坏的人又回到了原先的初始状态 ， 即与其他人没有连边 ， 本身没有电脑的情况 。

最后考虑回答 。

考虑该点所在的连通块状态 。

代码实现细节

综上 ， 我们需要维护这些操作 ：

  1. 连通块之间的合并
  2. 查找连通块内是否有环
  3. 分裂出某一个点
  4. 查找连通块状态

通过 1,2 两个操作可以非常敏锐地发现我们的算法 并查集 。

所以关键在于 3 操作如何维护 。

因为并查集的删除非常麻烦 ， 所以我们考虑不删除的做法 。

因为发现被删除的点即使留在联通块内也对答案没有任何影响 。

所以不妨对于每个人维护一个 id 代表这个人对应着 id 这个点 ， 每次删除只需要增加新的 id 并且把人对应这个新的 id 即可 。

代码

#include<bits/stdc++.h>
using namespace std;

const int N=13e5+7;
int n,m,f[N],id[N],cnt,x,sz[N],zt[N],y;
char opt;
//zt[]： 连通块的状态
int getf(int x)
{
    if(f[x]==x) return f[x];
    else return f[x]=getf(f[x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n+m;i++) f[i]=i;//并查集初始化
    for(int i=1;i<=n;i++) id[i]=i,sz[i]=1;//目前只有n个人
    cnt=n;//有用的 id 的个数
    for(int i=1,xx,yy;i<=m;i++)
    {
        cin>>opt;
        if(opt=='?')
        {
            scanf("%d",&x);
            x=id[x];
            xx=getf(x);
            if(sz[xx]==1) printf("%d",zt[xx]);// n=1 的情况
            else printf("%c",(zt[xx]?'1':'?'));
        }
        if(opt=='+')
        {
            scanf("%d%d",&x,&y);
            x=id[x]; y=id[y];
            xx=getf(x); yy=getf(y);
            if(xx==yy) zt[xx]=1; //联通块内成环
            else
            {
                sz[xx]+=sz[yy]; f[yy]=xx; zt[xx]|=zt[yy];// 合并连通块
            }
        }
        if(opt=='-')
        {
            scanf("%d",&x);
            xx=getf(id[x]); sz[xx]--; //删除
            id[x]=++cnt; sz[cnt]++; //增加新点
        }
    }
    return 0;
}