三種寫法:
．set 集合法(最慢, 容易 TLE)->NA:60%
．陣列 list 遍歷法(第二快, 遍歷陣列時會花比較多時間)->NA:70%
．樹根節點法 + 壓縮路徑(最快, 可通過)->AC:1.4s,3.7MB

補充資源 < 演算法筆記 >

集合法 <- 點擊可跳轉
陣列法 <- 點擊可跳轉
樹根法 <- 點擊可跳轉

輸入說明
第一行有三個正整數 N , M , Q (N <= 10000 , M <= 10000 , Q <= 100000)

代表有 N 個人 , M 筆朋友關係 , Q 筆詢問

接下來有 M 行， 每行有兩個正整數 A , B (A,B <= N)

代表 A 和 B 有 朋友 關係

再來有 Q 行， 每行兩個正整數 P , Q (A,B <= N)

輸出說明
請輸出 P 和 Q 是不是朋友

如果是請輸出 “:)”

否則請輸出 “:(“

樹根節點法

利用 Tree 結構加上路徑壓縮, 可以讓尋根的時間大幅縮短, 與陣列法差在路徑壓縮

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
def find_root(x): # 路徑壓縮法 -> 尋根時, 同時更新路徑【父節點 -> 根節點】
    global parent_list
    if parent_list[x]!=x:
        parent_list[x]=find_root(parent_list[x])
    return parent_list[x]

def link_tree(x,y):
    global parent_list
    x_root=find_root(x)
    y_root=find_root(y)
    if x_root!=y_root: # 根節點 (root) 不同, 即把兩根相連
        parent_list[y_root]=x_root

#step 1->read rule
N,M,Q=map(int,input().split())
parent_list=list(range(N+1)) # 用來存放父母節點, 初始化時, 每個人都是自己父母
#print(parent_list)

#step 2->set relationship
for i in range(0,M,1):
    temp1,temp2=map(int,input().split())
    link_tree(temp1,temp2)

#step 3->find friend
for i in range(0,Q,1):
    temp1,temp2=map(int,input().split())
    if find_root(temp1)==find_root(temp2):
        print(':)')
    else:
        print(':(')

#print()

陣列法

利用 list 陣列紀錄所有數的「group」, 默認等於 0, 當輸入兩數皆有群組 (group) 時, 遍歷陣列將兩者的 group 設為相同, 遍歷時會 TLE

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
N,M,Q=map(int,input().split())
friend_list=[0]*(N+1)
group=1
for i in range(0,M,1):
    temp1,temp2=map(int,input().split())
    if friend_list[temp1]==0 and friend_list[temp2]==0:
        friend_list[temp1]=group
        friend_list[temp2]=group
        group+=1
        #print(' 執行 1')
    elif friend_list[temp1]!=0 and friend_list[temp2]==0:
        friend_list[temp2]=friend_list[temp1]
        #print(' 執行 2')
    elif friend_list[temp1]==0 and friend_list[temp2]!=0:
        friend_list[temp1]=friend_list[temp2]
        #print(' 執行 3')
    else:
        ft1=friend_list[temp1]
        ft2=friend_list[temp2]
        friend_list=[ft1 if x == ft2 else x for x in friend_list] # 此行會 TLE
        #print(' 執行 4')

for i in range(0,Q,1):
    temp1,temp2=map(int,input().split())
    if temp1==temp2:
        print(':)')
    elif friend_list[temp1]==0 or friend_list[temp2]==0:
        print(":(")
    elif friend_list[temp1]!=friend_list[temp2]:
        print(":(")
    else:
        print(":)")

集合法

就…用太多迴圈了, 超沒效率

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
people,friend,ask=map(int,input().split())
temp=set(input().split())
friend_list=[temp]
point=1
check=False
for i in range(0,friend-1,1):
    temp=set(input().split())
    for j in range(0,point,1):
        if friend_list[j]&temp!=set():
            friend_list[j]=friend_list[j]|temp
            check=True
            break
    if check==False:
        friend_list.append(temp)
        point+=1
    # 初始化
    check=False

# 處理 friend_list 內的聯集
for i in range(0,len(friend_list)-1,1):
    for j in range(1+i,len(friend_list),1):
        if friend_list[i]&friend_list[j]!=set():
            friend_list[i]=friend_list[i].union(friend_list[j])
            friend_list[j]=friend_list[i].union(friend_list[j])

#friend 處理完畢

is_friend=False
for i in range (0,ask,1):
    temp=set(input().split())
    if len(temp)==1:
        print(":)")
        continue
    
    for j in range(0,point,1):
        if temp.issubset(friend_list[j]):
            print(":)")
            break
    else:
        print(":(")   
    # 初始化
    is_friend=False

a445. 新手訓練系列 - 我的朋友很少


作者: 微風