题解 P2835 【刻录光盘】

· · 个人记录

去他的并查集，这题根本不是并查集……来自并查集只有28分的蒟蒻的抱怨

我们把每个人向他愿意分享的人连一条单向边，然后自己画图瞎搞一下，很容易发现：

只有每个入度为0的点需要光盘！

所以我们只要在读入时记录每个点的入度，最后找有多少入度为0的点即可。

有了这个思想，你就……只有81分。别问我怎么知道的！

这个思想本身是没错的，但你有没有想过……图中出现环的情况呢？所有点入度都不为0。

这就十分尴尬。

我们再考虑特判一下。画个图你会发现：

只要图中有环，与这个环连通的所有点都只需要一个光盘。

这里的“连通”指有边连接，无论这条边指向哪里。

这就好办了，我们每次选择一个未被标记过的点（初始每个点都未被标记），把与这个点连通的所有点标记上（BFS），一直到所有点都被标记为止。选了多少次，则代表图中有多少个连通块，最后统计每个连通块的结果即可。

当然，要特别注意的是，同一个连通块中，如果有入度为0的点，则需要的光盘数等于入度为0的点的数量，否则为1。

上代码（附有简短注释）

#include<cstdio>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;

vector<int>g[202]; //我习惯用vector模拟邻接表
queue<int>q;

int n,ans=0,to,f[202]={0},zero;
//zero存储每个块中入度0的点，f数组记录入度

bool b[202]={0};

int main()
{
  int now,to,l,i,j;
  cin>>n;
  for(i=1;i<=n;i++)
  {
    scanf("%d",&to);
    while(to!=0)
    {
      g[i].push_back(to);
      g[to].push_back(i);//一定要连双向边！！！
      f[to]++;
      scanf("%d",&to);
    }
  }
  for(i=1;i<=n;i++)  //BFS
    if(!b[i])
    {
      zero=0;
      while(!q.empty()) q.pop();
      b[i]=true;
      q.push(i);
      while(!q.empty())
      {
        now=q.front();
        q.pop();
        if(!f[now]) zero++;
        l=g[now].size();
        for(j=0;j<l;j++)
        {
          to=g[now][j];
          if(!b[to])
          {
            b[to]=true;
            q.push(to);
          }
        }
      }
      ans+=max(1,zero);
    }
  cout<<ans;
  return 0;
}