leetcode:105. 有向图的完全联通
题目
【题目描述】
给定一个有向图，包含 N 个节点，节点编号分别为 1，2，...，N。现从 1 号节点开始，如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。
【输入描述】
第一行包含两个正整数，表示节点数量 N 和边的数量 K。 后续 K 行，每行两个正整数 s 和 t，表示从 s 节点有一条边单向连接到 t 节点。
【输出描述】
如果可以从 1 号节点的边可以到达任何节点，则输出 1，否则输出 -1。
思路
判断一个点是否可以到达其他点，就用DFS或者BFS，跟之前的岛屿问题很像。
比如说用dfs的话，还是有两种方式：
- dfs处理下一个节点
- dfs处理当前节点
跟之前一样，为了保证模版跟以前回溯那边的相同，我一般都会选择第2种方式。
深搜三部曲：
（1）确认递归函数、参数
参数包括：
- 整个地图graph
- 当前的这个节点，用key表示
- 已经走过的点visited
所以dfs写成：
void dfs(vector<vector<int>> &graph, int key, vector<bool> &visited)（2）终止条件
对于dfs第二种方式，我们在进入dfs的时候，立马进行终止条件判断：
就是如果这个key已经走过，那么这一层的dfs就可以停止。
（3）处理目前搜索节点出发的路径
我一般把这个叫下一步节点的处理或者周边节点的处理。
以前在岛屿问题里面，我们是设定了上下左右四个方向的数组，下一个节点那就是上下左右的节点，然后进行处理。
这里下一个节点就在邻接矩阵里面，所以我们遍历邻接矩阵，然后每一个进行dfs就行，这是跟岛屿问题的根本区别！！！
最终代码：
#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &graph, int key, vector<bool> &visited)
{
// 终止条件
if (visited[key])
return;
visited[key] = true;
vector<int> keys = graph[key];
for (int k : keys)
{
dfs(graph, k, visited);
}
}
int main()
{
int n, m, s, t;
cin >> n >> m;
// 建立邻接表
vector<vector<int>> graph(n + 1);
while (m--)
{
cin >> s >> t;
graph[s].push_back(t);
}
// 建立访问数组
vector<bool> visited(n + 1, false);
// 深搜：从1开始搜索整个地图
dfs(graph,1,visited);
// 检查是否所有节点都访问到了
for (int i = 1; i <= n; i++)
{
if (visited[i] == false)
{
cout << -1 << endl;
return 0;
}
}
cout << 1 << endl;
return 0;
}从节点1开始搜索整个地图，最后判断 visited数组是否所有的点都被标记上true。
总结
跟岛屿问题是差不多的，就是在dfs里面处理下一个节点，这里使用邻接表。