题解 P2835 【刻录光盘】

LMB_001 · 2017-07-01 20:10:13 · 题解

本题一开始我想用并查集，但普通的并查集是双向的，但本题是单向，用Floyd，在下不才，Pascal转c++刚一个星期，把Pascal的基础代入c++，特发一个c++帖，求大家不喜勿喷

#include <bits/stdc++.h>
using namespace std;  
int mapk[210][210],f[210];  //mapk表示一个人愿不愿意给另外一个人拷贝，也可以用布尔型，f表示一个人的父亲节点是哪个人
int main()  
{  
    int n,i,j,k,x;  
    while(cin >> n)  
    {  
        memset(mapk,0,sizeof(mapk));  //初始化
        for(i=1;i<=n;i++)  
            while(scanf("%d",&x),x)  //读入
               mapk[i][x]=1;  //表示第i个人愿意给第x个人拷贝
        for(k=1;k<=n;k++)  
            for(i=1;i<=n;i++)  
                for(j=1;j<=n;j++)  
                if(mapk[i][k]&&mapk[k][j])  
                    mapk[i][j]=1;//如果第i个人愿意给第k个人，而第k个人又愿意给第j个人，就相当于第i个人愿意给第j个人
       for(i=1;i<=n;i++)  
           f[i]=i;  //一开始，每个人的父亲节点就是自己
           for(i=1;i<=n;i++)  
            for(j=1;j<=n;j++)  
           if(mapk[i][j]) f[j]=f[i];  //如果i愿意给j拷贝，那么i的父亲节点就是j的父亲节点，注意别搞反了！
       int s=0;  
       for(i=1;i<=n;i++)  
           if(f[i]==i) s++;  //最后用循环扫一遍，如果i的父亲节点就是自己本身的话，计数器加一
        cout<<s<<endl;  //最后输出
    }  
    return 0;  
}  
大家注意看懂了再抄，不然还是不懂，我也思考了很久滴