f260. 愛八卦的同學

此題 zerojudge 遇到第二個測支會無法通過 (TLE), 所以自訂測支
一樣使用樹根節點法 + 路徑壓縮

輸入說明:

多筆測資

每筆測資第一行會有二個正整數 n , k (int)

n 代表班上的人數(編號為 0~n-1)，k 是接下來有幾筆關係

再來有 k 行，每行有二個整數 a , b 代表編號 a 跟 b 的人是朋友

輸出說明：

輸出總共有幾個小團體

小團體的定義是你的朋友或者是朋友的朋友跟你屬於同一個小團體

範例輸入:

5 6

1 0

0 1

1 2

2 3

2 4

4 1

5 4

1 0

0 1

2 3

2 4

範例輸出：

自訂測支

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: 
        parent_list[y_root]=x_root

while True:
    try:
        N,K=map(int,input().split())
        parent_list=list(range(N))     
        for i in range(0,K,1):
            temp1,temp2=map(int,input().split())
            link_tree(temp1,temp2)
        #print(parent_list)
        ans=[]

        for i in range(0,N,1):
            x=find_root(i)
            if not(x in ans):
                ans.append(x)

        print(len(ans))
        #print()
    except:
        break

f260. 愛八卦的同學

作者: 微風