PAT(Advanced Level) Practice（with python）——1118 Birds in Forest

code

N = int(input())

birds = [[] for i in range(10001)]
vis = [0 for i in range(10001)]
max_bird = 0
tree_id = 0

# 染色问题，并查集，如果没染色，深度搜索并染色
def dfs(cur):
    vis[cur] = tree_id
    for b in birds[cur]:
        if vis[b]==0:
            dfs(b)


for i in range(N):
    a, *b = map(int,input().split())
    max_bird = max(max_bird,max(b))
    for j in range(1,len(b)):
        x = b[j-1]
        y = b[j]
        birds[x].append(y)
        birds[y].append(x)

        
for i in range(1,max_bird+1):
    # 对没染色的bird进行染色，并深度搜索
    if vis[i]==0:
        tree_id+=1
        dfs(i)
print(tree_id,max_bird)


Q = int(input())
for q in range(Q):
    x,y = map(int,input().split())
    if vis[x]!=vis[y]:
        print("No")
    else:
        print("Yes")
# print(birds)
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