图论 11. 有向图的完全可达性

105. 有向图的完全联通

代码随想录

卡码网无难度标识

• 思路：

  这是比较简单的一道题

  • 有向图，求从起点结点1出发，是否能抵达其他所有结点
  • 所以只需要设定结点1为起点，然后图遍历直到所有能访问的结点都被访问了为止，然后再看访问表是否还有未访问节点即可

• dfs代码：

  import sys
  
  def dfs(graph, visited, s):
      # visited访问表，标记已访问结点
      # s为当前遍历节点
      visited[s] = True
  
      for node in graph[s]: # s的子结点
          if not visited[node]: # 未访问过的才进行拓展
              dfs(graph, visited, node)
  
  def main():
      # 有向图，求从起点结点1出发，是否能抵达其他所有结点
      # 所以只需要设定结点1为起点，然后图遍历直到所有能访问的结点都被访问了为止，然后再看访问表是否还有未访问节点即可
      lines = sys.stdin.readlines()
      n, k = map(int, lines[0].strip().split()) # 结点数量，边数量
      # 用邻接表构建图
      graph = [[] for _ in range(n+1)] # 由于结点编号1~n，为了索引能直接引用，多开一个
      for i in range(1, len(lines)):
          s, t = map(int, lines[i].strip().split()) # s -> t
          graph[s].append(t)
  
      visited = [False] * (n + 1) # 访问表，对应结点1~n
  
      dfs(graph, visited, 1)
  
      if False in visited[1:]: print(-1) # 注意这里要排除第0个元素，它没有对应的结点
      else: print(1)
  
  if __name__ == '__main__':
      main()
  

‍