题解 P2835 【刻录光盘】

嗯。 · 2018-07-30 21:27:57 · 个人记录

首先点开标签：缩点不会 并查集还行

于是兴高采烈地丢了个并查集模板上去，然后个点28分 美滋滋

然后仔细看了一下题，发现并不是双向边，那怎么用并查集来做呢

于是我想到了一个xjb 瞎鸡巴算法：先不管是不是双向边，直接合并，并记录入度为0的点（等下有用）

接下来我们发现入度为0的点必须要给光盘（因为没有人愿意给他们拷）。emm，于是ans+=入度为0的点的个数。

然后在每一个大集合中，除去入度为0的点，每个点在这一集合中都是可以联通的，所以只要统计大集合的个数就行了。

于是就nice地过了呀，QAQ;

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
int n,baba[201],b[201],ans=0;//baba数组记录每个点的爸爸，b数组之后用来统计入度的
inline int find(int x)//找祖先
{
    if(baba[x]==x)
    return x;
    return find(baba[x]);//路径压缩
}
inline void he(int x,int y)//合并操作
{
    int x1=find(x),y1=find(y);
    baba[y1]=baba[x1];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);//加速cin cout的，很有用
    cin>>n;
    for(int i=1;i<=n;i++)
    baba[i]=i,b[i]=0;//初始化
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        while(x!=0)//毒瘤题目 毒瘤读入
        {
            he(i,x);
            b[x]+=1;//统计入度
            cin>>x;
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(baba[i]==i)
        ans++;//大集合个数
        else
        {
            if(b[i]==0)
            ans++;//统计入度为0的个数
        }
    }
    cout<<ans;
    return 0;
}
//美滋滋