题解 P2835 【刻录光盘】

· · 个人记录

并查集的题怎么能没有并查集的解法呢

思路：并查集+乱搞

我们一开始想到用并查集

但后来发现只有20

这是为什么呢

发现并查集时会将两个点结成双向的边

即本来只能A给B，但是并查集之后B也能给A了

所以这样就会导致最终统计的光盘数减少

那么我们最后就需要将这些数再加回去

怎么搞？

先并查集一下

统计出祖先的个数，但这时并不是最终答案

我们需要将那些本来应该统计到自己是自己的祖先的点在统计一遍

#include<iostream>
using namespace std;
int f[1001],vis[1001][1001],book[1001];
int cnt,sum;
int getf(int x)       
{
    if(f[x]==x) return x;
    else
    {
        f[x]=getf(f[x]);
        return f[x];
    }
}
int merge(int x,int y)      //并查集的合并 
{
    int t1,t2;
    t1=getf(x),t2=getf(y);
    if(t1!=t2) f[t2]=t1;
}
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) f[i]=i;      //初始化 
    for(int i=1;i<=n;i++)        //读入+并查集 
    {
        int x,cnt=0;
        while(scanf("%d",&x),x)
        {
            cnt++;
            merge(i,x);
            vis[i][x]=1;
        }
        if(cnt==0) book[i]=1;       //统计没有归入到树中的节点 
    }
    for(int i=1;i<=n;i++)
    {
        if(f[i]==i)
        {
            sum++;            //并查集先统计祖先节点个数 
            book[i]=1;           //防止当前祖先在下面统计时重复统计 
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(book[i]==0)         //统计本来应该是祖先的节点的个数 
        {
            int flag=0;
            for(int j=1;j<=n;j++)        
            {
                if(vis[j][i]!=0)        //如果有别的人给他光盘，那么他不是祖先 
                {
                    flag=1;
                    break;
                }
            }
            if(flag==0) sum++;        //如果没有人给他光盘，那么他本来因该是祖先，光盘数+1 
        }
    }
    cout<<sum<<endl;
    return 0;
}