#41482: 不使用DFS與二分搜,單純用並查集做法


sophie19820517@gmail.com (闕河正)

學校 : 不指定學校
編號 : 115751
來源 : [123.110.172.57]
最後登入時間 :
2024-11-19 13:58:19
g598. 4. 真假子圖 -- 2021年11月APCS | From: [123.240.57.165] | 發表日期 : 2024-07-30 22:13

簡單來說,你的敵人是我的朋友

主要關鍵程式就在這

nf[k] ==>指向不是K的朋友中的根節點

解設你收到j,k  意思就是j與k不是朋友

換句話說不是k的朋友的根結點,就會是j的朋友的根結點

so 才有nf[j] = f[k],nf[k] = f[j]
for i in range(0,len(p) , 2):
        j,k = p[i] , p[i+1]
        if k in nf:
            jj = find(nf[k])
            set(j , jj)##set f[j]與他的快樂夥伴都以jj為根結點
        else:
            f[j] = j
        if j in nf:
            kk = find(nf[j])
            set(k , kk)
        else:
            f[k] = k
        nf[j] = f[k]
        nf[k] = f[j]

 
ZeroJudge Forum