Home PAT 1118 Birds in Forest
Post
Cancel

PAT 1118 Birds in Forest

Link

这题交了两遍才过, 第一遍为了省事没写 findFather, 导致忽略了一种情况:

当时写的是:

1
2
3
4
5
6
if(!indexes[id]) indexes[id]=i;
else if(indexes[id]==i) continue;
else{
    father[i]=father[indexes[id]]; //当时让father更新为旧值是想在for(i)里直接算出tree的说...
    indexes[id]=i;
}

想法是只要编号为 id 的鸟的 indexes 不为 0, 就说明在前面(甚至是当前)的照片中出现过, 而如果 indexes[id] 不为 0 但是等于 i 的时候, 说明编号为 id 的鸟是在当前照片中第一次出现, 所以不需要更新 father. 如果 indexes[id] 不为 0 但是不等于 i 的时候, 说明编号为 id 的鸟是在前面的照片中出现过, 所以需要更新 father. 于是我直接让当前的 father (当前就是指照片编号为 i) 等于照片编号为 indexes[id]father, 即 father[indexes[id]]. 这样就忽略了一种可能情况:

  • 照片编号 i1: father[i1]=i1;
  • 照片编号 i2 (i2>i1 且 i2>i3): father[i2]=father[i1], 是在遇到 indexes[id2]=i1 时更新的;
  • 照片编号 i2 (i2>i1 且 i2>i3): father[i2]=father[i3], 是在遇到 indexes[id3]=i3 时更新的;
  • father[i3]!=father[i1], 这就导致原本应该有的 father[i1]=father[i2]=father[i3] 不成立了.

也就是说, 当 i2i1 有交集、i2i3 有交集, 但是 i1i3 没有交集时, i2father 值只会更新为 i1i3 中后出现的那一个.

因此, 不要偷懒, 想清楚再编码! 把 findFather 写上! (不然根本没省事, 还 debug 了半天…)

AC 代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int n,k,id,q,x,y,tree,num;
int indexes[10010],father[10010];
int findFather(int x){
    while(father[x]!=x) x=father[x]=father[father[x]];
    return x;
}
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        father[i]=i;
        scanf("%d",&k);
        for(int j=1;j<=k;++j){
            scanf("%d",&id);
            num=max(num,id);
            if(!indexes[id]) indexes[id]=i;
            else if(indexes[id]==i) continue;
            else{
                father[indexes[id]]=father[i];
                indexes[id]=i;
            }
        }
    }
    for(int i=1;i<=n;++i)
        if(father[i]==i)
            tree++;
    printf("%d %d\n",tree,num);
    scanf("%d",&q);
    while(q--){
        scanf("%d%d",&x,&y);
        if(findFather(indexes[x])==findFather(indexes[y]))
            printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
This post is licensed under CC BY 4.0 by the author.