题目描述

小A参加一个n人的活动，每个人都有一个编号（0<=i<=n-1），其中有m对相互认识，在活动中两个人可以通过互相都认识都认识的一个人介绍认识。现在问活动结束后，小A最多会新认识多少人？
输入:
第一行是聚会人数n
第二行是小A的编号a
接下来m行为互相认识的对，以’,'分割
输出：
小A最多会新认识多少人的人数。
样例输入：
7
5
6
1,0
3,1
4,1
5,3
6,1
6,5
样例输出：
3
提示：
小A新认识的人为【0，1，4】

深度遍历

1.分析这句话“个人可以通过互相都认识都认识的一个人介绍认识”，所以最终，有间接认识关系的人都会互相认识。

2.该问题是一个无向图的深度遍历。深度递归到的节点都是小A的朋友（包括初始朋友和新朋友）。

3.在深度遍历的过程中，把小A新认识的人加入一个集合中，最后输出这个集合的长度。

4.注意不要把小A和小A初始已经认识的朋友加入集合中

5.考虑到整个图可能是不连通的，所以必须从a开始进行深度遍历

n = eval(input())
a = eval(input())
m = eval(input())
from collections import defaultdict
d = defaultdict(list)
for i in range(m):
    start,end  = map(int,input().split(','))
    d[start].append(end)
    d[end].append(start)

visited = [False]*n
visited[a] = True
friend = set()

def recur(i):
    if (i != a) and (i not in d[a]):
    	#注意不要把小A和小A初始已经认识的朋友加入集合中
        friend.add(i)
    if (d[i] == []):
        return
    for re in d[i]:
        if visited[re] == False:
            visited[re] = True
            recur(re)
            #visited[re] = False
            #注意这里在递归回来时不用恢复visited，因为在这里只需要考虑深度遍历到的有哪些节点
            #而是不是新朋友，交给递归函数里的第一个if判断就可以了
            #加了这句反而会使有些节点被重复得递归到
            
recur(a)
print(len(friend))

该代码中如果没有注释掉visited[re] = False，有些递归分支会作一些无用功。比如递归到6后，会递归到1；而递归到3后，又会递归到1（之后还有重复的递归）。

思考与总结

虽然你看我现在思路这么清晰，当时笔试的时候却理解错了题意，我以为输出集合是【3，6，1】，因为以为此题是深度遍历但最大深度为2，然后代码通过率一直只有67%（多亏测试用例“设计得好”，不然我感觉连67%都没有，手动苦瓜脸）。做题还是应该把题意理解清楚了再做。

看来我是没有机会用爱发电了，债见B站。

最后

以上就是粗暴美女为你收集整理的哔哩哔哩2018.9.21笔试 小A最多会新认识多少人题目描述深度遍历思考与总结的全部内容，希望文章能够帮你解决哔哩哔哩2018.9.21笔试 小A最多会新认识多少人题目描述深度遍历思考与总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。