小A最多会新认识的多少人

[编程题]小A最多会新认识的多少人

热度指数：5829 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小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最多会新认识的多少人？

示例1

输入

7
5
6
1,0
3,1
4,1
5,3
6,1
6,5

输出

算法知识视频讲解

Python3

跑路狂魔

from collections import defaultdict
while True:
try:
n=int(input())
a=int(input())
m=int(input())
d=defaultdict(set)
for _ in range(m):
p,c=[int(each) for each in input().split(',')]
d[p].add(c)
d[c].add(p)
have_known=len(d[a])
temp=set()
while temp!=d[a]:
new=d[a]-temp
temp=d[a].copy()
for item in new:
for j in d[item]:
d[a].add(j)
all_known=[each for each in d[a] if each != a]
print(len(all_known)-have_known)
except:
break

发表于 2022-05-07 16:46:05 回复(0)