w网站制作和推广长沙做网站推广公司咨询

在考察输入输出方面我觉得是道难题了 第一次遇见邻接表的数据结构该怎么声明  

卡码网105   在力扣没找见完全相同的题    感觉需要多练习多复习这种类型的题

105. 有向图的完全可达性

题目描述

给定一个有向图，包含 N 个节点，节点编号分别为 1，2，...，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

输入描述

第一行包含两个正整数，表示节点数量 N 和边的数量 K。 后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。

输出描述

如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。

输入示例

4 4
1 2
2 1
1 3
2 4

输出示例

1

提示信息

从 1 号节点可以到达任意节点，输出 1。

数据范围：

1 <= N <= 100；
1 <= K <= 2000。

思路：  深搜 1.确认递归函数 参数 
      需要传入地图，需要知道当前我们拿到的key，以至于去下一个房间(节点）。
同时还需要一个数组，用来记录我们都走过了哪些房间，
这样好知道最后有没有把所有房间都遍历的，可以定义一个一维数组。

Dfs时的终止条件判断  ：如果我们是处理当前访问的节点，当前访问的节点如果是 true ，
说明是访问过的节点，那就终止本层递归，如果不是true，我们就把它赋值为true，
因为这是我们处理本层递归的节点。

需要注意的点：1.  List<List<int>> graph=new List<List<int>>(n+1); 数据结构 

List<List<int>> 是一个嵌套的 List 类型，表示一个包含多个整数列表的列表。可以把它看作是一个列表的列表。 

1. graph 是一个 List<List<int>> 类型的变量，表示图的邻接表。它包含 n + 1 个 List<int> 元素，代表图中的 n + 1 个节点。
2. 每个 List<int> 用来存储该节点的邻接节点。通过 graph[i].Add(x) 的方式，将节点 i 与其他节点 x 连接起来。
3. 使用 string.Join(", ", graph[i]) 将每个列表中的元素格式化成字符串并打印出来，展示图的邻接关系。

2.List<int> suroudkey= graph[key];  这一部分的意思是检测到的key节点的相连接的节点取出来 为suroudkey列表中的数 其中的数就是相邻的节点

• graph 是一个 邻接表，即 List<List<int>> 类型的数据结构，其中 graph[key] 代表节点 key 的所有邻接节点（即节点 key 直接相连的节点列表）。
• suroudkey是一个 List<int>，保存了 key 节点的所有邻接节点的列表。  

1. 访问当前节点：在调用 Dfs 函数时，当前节点会被访问。通常，DFS 会通过一个 visited 数组（或集合）来记录哪些节点已经被访问过，以避免重复访问。
2. 遍历邻接节点：在 graph[key] 中，找出当前节点 key 所有直接相连的邻接节点，即 keys。对每一个邻接节点 nextKey，递归地调用 Dfs 函数进行深度优先遍历。
3. 递归过程：递归调用会继续深入到下一个未被访问的邻接节点，直到遍历完当前节点的所有邻接节点。然后回溯到上一个节点，继续访问下一个未被访问的邻接节点。

代码实现：

using System;
using System.Collections.Generic;

class Program
{
        static void Main()
        {
                  //输入模式
             string[] input= Console.ReadLine().Split();
              int n=int.Parse(input[0]);
              int k=int.Parse(input[1]);
          
          //难点：需要进行邻接表初始化 
          //这个数据结构放到开头解释 
            List<List<int>> graph=new List<List<int>>(n+1);
            for(int i=0;i<=n;i++)
            {
                graph.Add(new List<int>());
            }
            //输入除第一行之外的信息  （边的信息）
              for(int i=0;i<k;i++)
              {
                  string[] edge=Console.ReadLine().Split();
                  s=int.Parse(edge[0]);
                  t=int.Parse(edge[1]);
                  //使用邻接表 表示s-》t是相连的
                  graph[s].Add(t);
              }
              
              //访问标记数值 这就是我们说的用来记录录都走过了哪些房间的一维数组
              bool[] visted=new bool[n+1];
              // 从节点一开始进行Dfs遍历 
              Dfs(graph,1,visted);
              //检测是否所有节点都被访问到了 
              for(int i=1;i<=n;i++)
              {
                  if(visted[i]==false) //如果检测了一遍发现有false 证明有的节点没被访问
                  {
                      //输出-1 
                      Console.WriteLine(-1);
                      return ;
                  }
                  //如果检测到的全部都为true 证明全被访问了 输出1 
                  Console.WriteLine(1);
              }
        }
      
      public static void Dfs( List<List<int>> graph,int key,bool[] visted)
      {
          //处理当前访问节点 
          if(visted[key]==true)
          {
                return ;
          }
          //因为默认数组中都是false 所以访问一个变一个 
          
          visted [key]=true;
          
          List<int> suroudkey=graph[key];//找出当前key的所有相连节点
          //开始遍历相连的key 因为是一个列表 都存着数 就直接遍历就行
          foreach(int nextkey in suroudkey )
          {
              Dfs(graph,nextkey,visted);
          }
      }
      
}