代码随想录算法训练营第五十八天| 图论4—卡码网110. 字符串接龙，105. 有向图的完全联通

图论第四天，感觉图论+ACM每道题做的都挺麻烦的，需要花很多时间，题目花样还是挺多的，需要思考每道题怎么去搜索，如果知道思路之后做起来还是比较轻松的。

110. 字符串接龙

110. 字符串接龙

思路新颖，题目简单的一道题，因为每次只能变一个字符，所以judge函数就是查找只有一个字符不同的两个字符串，组成可以行走的路径。然后才是利用bfs进行遍历，每走一步，将当前的字符在visited中的表示转为True，以免走回头路。所以就是为什么bfs的判断条件是if visit[i]==False and judge(strlist[i],str):只有没走过+只差1的才可以走，然后将当前字符串以及该字符串所走的步数进行记录，有点像之前的二叉树高度计算，以后序遍历初步的将每个节点的高度往上进行传递，这个也是将每个字符串的步骤进行传递。当当前的str和endstr相等的时候，结束递归并输出当前的步数，如果没有的话则输出0。

def judge(s1,s2):count=0for i in range(len(s1)):if s1[i]!=s2[i]:count+=1return count==1if __name__=='__main__':n=int(input())beginstr,endstr=map(str,input().split())if beginstr==endstr:print(0)exit()strlist=[]for i in range(n):strlist.append(input())# use bfsvisit=[False for i in range(n)]queue=[[beginstr,1]]while queue:str,step=queue.pop(0)if judge(str,endstr):print(step+1)exit()for i in range(n):if visit[i]==False and judge(strlist[i],str):visit[i]=Truequeue.append([strlist[i],step+1])print(0)

105. 有向图的完全联通

105. 有向图的完全联通

题目确实是多种多样的，但是BFS的思路变化都挺小，主要思路还是创捷队列，然后进行弹出，将弹出的元素进行操作，比如这道题中就是加入到path中。 BFS 从节点1开始遍历图，通过维护que 扩展节点，将所有能到达的节点加入。最后判断是否包含了1到n的所有节点。如果相等，说明图是连通的，从起点能访问所有节点。

import collectionspath = set() def bfs(root, graph):global pathque = collections.deque([root])while que:cur = que.popleft()path.add(cur)for nei in graph[cur]:que.append(nei)graph[cur] = []returndef main():N, K = map(int, input().strip().split())graph = collections.defaultdict(list)for _ in range(K):src, dest = map(int, input().strip().split())graph[src].append(dest)bfs(1, graph)if path == {i for i in range(1, N + 1)}:return 1return -1if __name__ == "__main__":print(main())