题解 P2835 【刻录光盘】

· · 个人记录

博客阅读体验更佳

简（du）单（liu）样例

如果 WA 声一片的可以测测这个样例：

输入 输出

展开源码复制即可。

样例选自 Viston 的题解

前置芝士

并查集，并查集的灵活应用。

题目分析

如果不知道什么是并查集的话珂以参考我的这篇题解。

乍一看，这不是并查集的模板吗？进行若干次合并操作后判断有几个集合就行了。

于是，只有 9 分。

究竟错在哪儿了呢？原来，并查集是“双向”的，而题目的关系是“单向”的，那么怎么处理呢？（没有头绪的人跟我念：无论遇到什么困难，也不要怕……）

我们可以记录下每个节点的“入度”，即有多少个人愿意拷给他，如果“入度”为 0，那么就需要单独刻一个光盘，但是，如果他是并查集的“根”的话就不要单独刻了，因为他不管怎么样都要刻一个。

代码实现

具体见注释：

#include<bits/stdc++.h>
using namespace std;
int f[205],ind[205];//并查集 入度
int n,ans;
void init()//初始化
{
    for(int i=1;i<=205;i++) f[i]=i;
}
int find(int x)//并查集之 find
{
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void _union(int x,int y)//并查集之 union，因为数据量小，所以无需启发式合并
{
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy) f[yy]=xx;//这里不能写反，因为边是有向的 
}
int main()
{
    init();
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;//输入，不能把这句写到循环里面，否则会把 0 给读进去
        while(x!=0)
        {
            ind[x]++;
            _union(i,x);
            cin>>x;
        } 
    }
    for(int i=1;i<=n;i++)//统计
    {
        if(f[i]==i) ans++;//发现一个集合，即祖先还是自己
        else if(ind[i]==0) ans++;//如果不是祖先且没有人拷给他，需要另外刻一个
    }
    cout<<ans;//输出
    return 0;//完结撒花
}