题解 P2835 【刻录光盘】

· · 个人记录

核心思想

并查集....

然而我们发现这题用传统的并查集会WA,为什么？

因为并查集是双向的。

就比如说：

有五个点1,2,3,4,5;

$2$给$4,5$拷贝, $3$给$4$拷贝, $4,5$不给别人。 那么我们就会发现了,$3$的父亲会变成$1,

然后程序就会输出1,就愉快的WA了！

我们可以这样思考:

我们不管那些特殊点（比如3），用一个数组存一下每一个点有没有直系的父亲,其他的跟并查集没啥区别。

最后O(n) 扫一遍的时候加以判断，如果是没有直系父亲的，直接加一，其他的如果是祖先也加一。

拜拜，满分QAQ
按道理说是0ms....

#include<bits/stdc++.h>
int a,b,c,j,f[202],q[202],ans;
inline int find(int x){             并查集
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
int main(){
    std::cin>>a;
    for(register int i=1;i<=a;i++)f[i]=i;          初始化
    for(register int i=1;i<=a;i++){
        b=find(i);
        while(1){
            int d;std::cin>>d;
            if(d==0) break;
            q[d]=1;                 标记一下他有直系父亲
            c=find(d);
            if(c!=b)f[c]=b;
        }
    }
    for(register int i=1;i<=a;i++)
    if(f[i]==i||q[i]==0)ans++;     最后加以判断
    std::cout<<ans;
    return 0;
}