AcWing 1189. 刻录光盘    原题链接    简单

作者： 作者的头像   小菜鸡UP ,  2020-05-03 15:31:57 ,  所有人可见 ,  阅读 789

4


刚开始单纯的我写了传统的并查集发现WA了，这是因为传统并查集建的关系是双向的。而本题建立的是单向的关系

比如1给2；2给4，5；3给4；如果传统的并查集，那么3的祖宗节点是1了，显然不符合题意

那么我们再思考发现，如果一个点是祖宗节点，光盘是要给的，还有一种情况是一个点是孤儿，那么这个点是要给光盘的。除此之外的点说明入度(有人给)不为0，那么一定有别人给，追根到底就是祖宗；

对于一个点的入度我们在合并节点的时候统计

还有这题的输入输出，我自己脑抽写了个stirng.getline去做，还要写多位数，直接快排模板叭

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1e5;
typedef long long LL;
int p[maxn],inn[maxn];
int find(int x)
{
    if(x!=p[x]) return p[x]=find(p[x]); 
    return p[x];
}
inline int read()//快读板子
{
    int x = 0, f = 1;
    char ch = getchar();
    if (ch == '-')
        f = -1, ch = getchar();
    while(ch<'0'||ch>'9')
        ch = getchar();
    while(ch<='9'&&ch>='0')
    {
        x = x * 10 + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
int main(void)
{
    int n=read();
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=n;i++)
    {
        int str=read();
        while(str!=0)
        {
            p[find(str)]=find(i);
            inn[str]++;
            str=read();
        }
    }
    int sum=0;
    for(int i=1;i<=n;i++)
    {
        if(p[i]==i) sum++;
        else if(inn[i]==0) sum++;
    }
    cout<<sum<<endl;
return 0;
}

1 评论

用户头像
OYSHOWJ   2023-02-03 21:25      1    踩      回复

并查集会被hack

32
18 21 23 30 22 26 25 12 19 7 29 0
19 20 16 25 8 4 11 18 1 0
12 30 21 27 23 6 4 1 19 31 5 24 11 29 20 16 0
25 2 10 8 12 24 30 14 22 1 26 7 19 16 17 28 23 21 15 31 20 29 0
0
22 4 19 14 25 23 18 16 21 28 9 10 11 3 17 8 27 26 12 20 2 29 31 15 1 5 24 30 7 13 0
28 9 18 25 14 3 21 31 13 17 6 20 23 30 0
10 26 19 29 14 1 4 17 18 5 13 31 22 24 16 20 21 25 2 6 9 28 30 7 15 12 23 3 11 27 0
1 11 22 15 23 16 28 29 0
17 0
27 2 18 6 5 25 10 26 28 23 9 29 20 8 19 12 1 13 21 14 3 15 31 24 0
28 31 30 24 0
0
4 29 21 19 24 31 20 6 17 22 26 1 13 23 16 7 27 2 18 8 12 30 10 15 25 3 0
30 19 17 18 7 2 24 20 25 26 16 11 14 8 1 23 5 0
24 7 8 15 31 0
27 1 25 11 10 0
31 17 19 9 5 13 16 6 25 14 21 29 28 27 8 11 22 26 1 0
15 31 7 18 22 13 16 29 26 11 25 5 24 8 28 23 30 17 14 4 9 12 21 6 27 3 1 20 10 0
0
19 9 8 25 11 17 0
31 8 15 6 12 9 23 17 7 13 24 4 26 10 14 18 30 28 16 19 0
29 12 24 21 18 1 9 7 28 0
23 21 17 4 12 0
16 9 18 8 4 12 28 31 22 29 10 21 27 24 1 23 7 2 5 30 17 3 15 6 20 19 26 13 14 0
11 23 14 5 25 8 16 19 6 3 12 22 29 31 21 10 13 0
1 0
15 13 6 16 4 3 24 7 29 27 19 18 14 2 31 26 21 17 12 8 1 5 30 23 22 0
19 20 22 10 28 31 12 24 2 3 13 14 9 16 5 25 27 23 17 26 21 0
26 28 25 7 29 14 16 1 5 4 12 22 3 15 2 6 21 11 19 20 23 0
20 11 30 17 3 28 14 16 15 2 24 8 13 27 9 1 18 0
13 0

答案是 2 ，但是并查集做出来的答案是1