在考察輸入輸出方面我覺(jué)得是道難題了 第一次遇見(jiàn)鄰接表的數(shù)據(jù)結(jié)構(gòu)該怎么聲明??

卡碼網(wǎng)105? ?在力扣沒(méi)找見(jiàn)完全相同的題? ? 感覺(jué)需要多練習(xí)多復(fù)習(xí)這種類型的題

105. 有向圖的完全可達(dá)性

題目描述

給定一個(gè)有向圖，包含 N 個(gè)節(jié)點(diǎn)，節(jié)點(diǎn)編號(hào)分別為 1，2，...，N?，F(xiàn)從 1 號(hào)節(jié)點(diǎn)開(kāi)始，如果可以從 1 號(hào)節(jié)點(diǎn)的邊可以到達(dá)任何節(jié)點(diǎn)，則輸出 1，否則輸出 -1。

輸入描述

第一行包含兩個(gè)正整數(shù)，表示節(jié)點(diǎn)數(shù)量 N 和邊的數(shù)量 K。 后續(xù) K 行，每行兩個(gè)正整數(shù) s 和 t，表示從 s 節(jié)點(diǎn)有一條邊單向連接到 t 節(jié)點(diǎn)。

輸出描述

如果可以從 1 號(hào)節(jié)點(diǎn)的邊可以到達(dá)任何節(jié)點(diǎn)，則輸出 1，否則輸出 -1。

輸入示例

4 4
1 2
2 1
1 3
2 4

輸出示例

1

提示信息

從 1 號(hào)節(jié)點(diǎn)可以到達(dá)任意節(jié)點(diǎn)，輸出 1。

數(shù)據(jù)范圍：

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

思路：??深搜 1.確認(rèn)遞歸函數(shù) 參數(shù)?
? ? ? 需要傳入地圖，需要知道當(dāng)前我們拿到的key，以至于去下一個(gè)房間(節(jié)點(diǎn)）。
同時(shí)還需要一個(gè)數(shù)組，用來(lái)記錄我們都走過(guò)了哪些房間，
這樣好知道最后有沒(méi)有把所有房間都遍歷的，可以定義一個(gè)一維數(shù)組。

Dfs時(shí)的終止條件判斷 ?：如果我們是處理當(dāng)前訪問(wèn)的節(jié)點(diǎn)，當(dāng)前訪問(wèn)的節(jié)點(diǎn)如果是 true ，
說(shuō)明是訪問(wèn)過(guò)的節(jié)點(diǎn)，那就終止本層遞歸，如果不是true，我們就把它賦值為true，
因?yàn)檫@是我們處理本層遞歸的節(jié)點(diǎn)。

需要注意的點(diǎn)：1.? List<List<int>> graph=new List<List<int>>(n+1); 數(shù)據(jù)結(jié)構(gòu)?

List<List<int>> 是一個(gè)嵌套的 List 類型，表示一個(gè)包含多個(gè)整數(shù)列表的列表?？梢园阉醋魇且粋€(gè)列表的列表。?

1. graph?是一個(gè)?List<List<int>>?類型的變量，表示圖的鄰接表。它包含?n + 1?個(gè)?List<int>?元素，代表圖中的?n + 1?個(gè)節(jié)點(diǎn)。
2. 每個(gè)?List<int>?用來(lái)存儲(chǔ)該節(jié)點(diǎn)的鄰接節(jié)點(diǎn)。通過(guò)?graph[i].Add(x)?的方式，將節(jié)點(diǎn)?i?與其他節(jié)點(diǎn)?x?連接起來(lái)。
3. 使用?string.Join(", ", graph[i])?將每個(gè)列表中的元素格式化成字符串并打印出來(lái)，展示圖的鄰接關(guān)系。

2.List<int> suroudkey= graph[key];? 這一部分的意思是檢測(cè)到的key節(jié)點(diǎn)的相連接的節(jié)點(diǎn)取出來(lái) 為suroudkey列表中的數(shù) 其中的數(shù)就是相鄰的節(jié)點(diǎn)

• graph?是一個(gè)?鄰接表，即?List<List<int>>?類型的數(shù)據(jù)結(jié)構(gòu)，其中?graph[key]?代表節(jié)點(diǎn)?key?的所有鄰接節(jié)點(diǎn)（即節(jié)點(diǎn)?key?直接相連的節(jié)點(diǎn)列表）。
• suroudkey是一個(gè)?List<int>，保存了?key?節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)的列表。??

1. 訪問(wèn)當(dāng)前節(jié)點(diǎn)：在調(diào)用?Dfs?函數(shù)時(shí)，當(dāng)前節(jié)點(diǎn)會(huì)被訪問(wèn)。通常，DFS 會(huì)通過(guò)一個(gè)?visited?數(shù)組（或集合）來(lái)記錄哪些節(jié)點(diǎn)已經(jīng)被訪問(wèn)過(guò)，以避免重復(fù)訪問(wèn)。
2. 遍歷鄰接節(jié)點(diǎn)：在?graph[key]?中，找出當(dāng)前節(jié)點(diǎn)?key?所有直接相連的鄰接節(jié)點(diǎn)，即?keys。對(duì)每一個(gè)鄰接節(jié)點(diǎn)?nextKey，遞歸地調(diào)用?Dfs?函數(shù)進(jìn)行深度優(yōu)先遍歷。
3. 遞歸過(guò)程：遞歸調(diào)用會(huì)繼續(xù)深入到下一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)，直到遍歷完當(dāng)前節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)。然后回溯到上一個(gè)節(jié)點(diǎn)，繼續(xù)訪問(wèn)下一個(gè)未被訪問(wèn)的鄰接節(jié)點(diǎn)。

代碼實(shí)現(xiàn)：

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]);
? ? ? ? ??
? ? ? ? ? //難點(diǎn)：需要進(jìn)行鄰接表初始化?
? ? ? ? ? //這個(gè)數(shù)據(jù)結(jié)構(gòu)放到開(kāi)頭解釋?
? ? ? ? ? ? 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);
? ? ? ? ? ? ? }
? ? ? ? ? ? ??
? ? ? ? ? ? ? //訪問(wèn)標(biāo)記數(shù)值 這就是我們說(shuō)的用來(lái)記錄錄都走過(guò)了哪些房間的一維數(shù)組
? ? ? ? ? ? ? bool[] visted=new bool[n+1];
? ? ? ? ? ? ? // 從節(jié)點(diǎn)一開(kāi)始進(jìn)行Dfs遍歷?
? ? ? ? ? ? ? Dfs(graph,1,visted);
? ? ? ? ? ? ? //檢測(cè)是否所有節(jié)點(diǎn)都被訪問(wèn)到了?
? ? ? ? ? ? ? for(int i=1;i<=n;i++)
? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? if(visted[i]==false) //如果檢測(cè)了一遍發(fā)現(xiàn)有false 證明有的節(jié)點(diǎn)沒(méi)被訪問(wèn)
? ? ? ? ? ? ? ? ? {
? ? ? ? ? ? ? ? ? ? ? //輸出-1?
? ? ? ? ? ? ? ? ? ? ? Console.WriteLine(-1);
? ? ? ? ? ? ? ? ? ? ? return ;
? ? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? ? //如果檢測(cè)到的全部都為true 證明全被訪問(wèn)了 輸出1?
? ? ? ? ? ? ? ? ? Console.WriteLine(1);
? ? ? ? ? ? ? }
? ? ? ? }
? ? ??
? ? ? public static void Dfs( List<List<int>> graph,int key,bool[] visted)
? ? ? {
? ? ? ? ? //處理當(dāng)前訪問(wèn)節(jié)點(diǎn)?
? ? ? ? ? if(visted[key]==true)
? ? ? ? ? {
? ? ? ? ? ? ? ? return ;
? ? ? ? ? }
? ? ? ? ? //因?yàn)槟J(rèn)數(shù)組中都是false 所以訪問(wèn)一個(gè)變一個(gè)?
? ? ? ? ??
? ? ? ? ? visted [key]=true;
? ? ? ? ??
? ? ? ? ? List<int> suroudkey=graph[key];//找出當(dāng)前key的所有相連節(jié)點(diǎn)
? ? ? ? ? //開(kāi)始遍歷相連的key 因?yàn)槭且粋€(gè)列表 都存著數(shù) 就直接遍歷就行
? ? ? ? ? foreach(int nextkey in suroudkey )
? ? ? ? ? {
? ? ? ? ? ? ? Dfs(graph,nextkey,visted);
? ? ? ? ? }
? ? ? }
? ? ??
}
?