小A参加了一个n人的活动,每个人都有一个唯一编号i(i>=0 & i<n),其中m对相互认识,在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后,小A最多会认识多少人?
小A参加了一个n人的活动,每个人都有一个唯一编号i(i>=0 & i<n),其中m对相互认识,在活动中两个人可以通过互相都认识的一个人介绍认识。现在问活动结束后,小A最多会认识多少人?
第一行聚会的人数:n(n>=3 & n<10000);
第二行小A的编号: ai(ai >= 0 & ai < n);
第三互相认识的数目: m(m>=1 & m
< n(n-1)/2);
第4到m+3行为互相认识的对,以','分割的编号。
输出小A最多会新认识的多少人?
7 5 6 1,0 3,1 4,1 5,3 6,1 6,5
3
class DSU: def __init__(self,n: int): self.p = [i for i in range(n)] self.cnt = [1] * n def find(self,x: int) -> int: if x != self.p[x]: self.p[x] = self.find(self.p[x]) return self.p[x] def merge(self,x: int,y: int): rx , ry = self.find(x) , self.find(y) if rx == ry: return self.p[rx] = ry self.cnt[ry] += self.cnt[rx] return def main(): n = int(input()) dsu = DSU(n) p = int(input()) m = int(input()) res = 0 for _ in range(m): a ,b = map(int,input().split(',')) if a == p: res -= 1 if b == p: res -= 1 dsu.merge(a,b) fa = dsu.find(p) print(dsu.cnt[fa] + res - 1) if __name__ == '__main__': main()并查集模版题