题目分析

这个题目思路很清晰，首先想到两种方法，DFS和BFS，但是要注意如何去解决关系中出现环的情况。

DFS

深度优先搜索，就是从那个人开始，一直往下搜索，如果找不到可以联系的人，则记录当前的关系并和已知最远关系进行比较，如果大于最远关系，则赋值给最远关系，并回溯。如果在搜索的过程中发现下一个人出现在已经搜索到的人之中，则回溯，防止出现死循环。

import sys


def dfs(current_people, current_relationship):
    global result

    for neighbor in range(1, n + 1):
        if relationship[current_people][neighbor] == 1 and str(neighbor) not in current_relationship:
            dfs(neighbor, current_relationship + str(neighbor))

    if len(current_relationship) > len(result):
        result = current_relationship


for line in sys.stdin:
    n, m = [int(x) for x in line.strip().split()]
    relationship = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(m):
        a, b = [int(x) for x in sys.stdin.readline().strip().split()]
        relationship[a][b] = 1
        relationship[b][a] = 1
    p = int(sys.stdin.readline().strip())
    result = ''
    dfs(p, str(p))
    print(result)

BFS

广度优先搜索，就是从那个人开始，将他可以联系到的所有人都记录下来，并称之为朋友，然后再寻找他朋友的朋友，即将和他朋友的朋友都记录下来，然后再寻找他朋友的朋友的朋友。如果再搜索时发现某个朋友已经出现在寻找的路径之中，则不继续搜索这个路径，每次迭代后关系就会增加一轮，直到最远的关系被找到为止。

import sys


for line in sys.stdin:
    n, m = [int(x) for x in line.strip().split()]
    relationship = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(m):
        a, b = [int(x) for x in sys.stdin.readline().strip().split()]
        relationship[a][b] = 1
        relationship[b][a] = 1
    p = int(sys.stdin.readline().strip())
    result = ''
    queue = [[p, str(p)]]
    while queue:
        result = queue[-1]
        current_people, current_relationship = queue.pop(0)
        for neighbor in range(1, n + 1):
            if relationship[current_people][neighbor] == 1 and str(neighbor) not in current_relationship:
                queue.append([neighbor, current_relationship + str(neighbor)])
    print(result[-1])

刷题总结

BFS和DFS是两种重要的路径搜索方法，在绝大多数情况下，两种方法可以相互转换，小伙伴们一定要掌握它。