802_找到最终的安全状态C++_c++ 802. 找到最终的安全状态

题目：在有向图中, 我们从某个节点和每个转向处开始, 沿着图的有向边走。 如果我们到达的节点是终点 (即它没有连出的有向边), 我们停止。

现在, 如果我们最后能走到终点，那么我们的起始节点是最终安全的。 更具体地说, 存在一个自然数 K, 无论选择从哪里开始行走, 我们走了不到 K 步后必能停止在一个终点。

哪些节点最终是安全的？ 结果返回一个有序的数组。

该有向图有 N 个节点，标签为 0, 1, …, N-1, 其中 N 是 graph 的节点数. 图以以下的形式给出: graph[i] 是节点 j 的一个列表，满足 (i, j) 是图的一条有向边。

这道题给了我们一个有向图，然后定义了一种最终安全状态的结点，就是说该结点要在自然数K步内停止，所谓停止的意思，就是再没有向外的边，即没有出度，像上面例子中的结点5和6就是出度为0，因为graph[5]和graph[6]均为空。那么我们分析题目中的例子，除了没有出度的结点5和6之外，结点2和4也是安全状态结点，为啥呢，我们发现结点2和4都只能到达结点5，而结点5本身就是安全状态点，所以2和4也就是安全状态点了，所以我们可以得出的结论是，若某结点唯一能到达的结点是安全状态结点的话，那么该结点也同样是安全状态结点。

于是可以考虑方法一：我们就可以从没有出度的安全状态往回推，比如结点5，往回推可以到达结点4和2，先看结点4，此时我们先回推到结点4，然后将这条边断开，那么此时结点4出度为0，则标记结点4也为安全状态结点，同理，回推到结点2，断开边，此时结点2虽然入度仍为2，但是出度为0了，标记结点2也为安全状态结点。

分析到这里，思路应该比较明朗了，由于我们需要回推边，所以需要建立逆向边，用一个集合数组来存，由于题目要求返回的结点有序，我们可以利用集合TreeSet的自动排序的特性，由于需要断开边，为了不修改输入数据，所以我们干脆再建一个顺向边得了，即跟输入数据相同。还需要一个safe数组，布尔型的，来标记哪些结点是安全状态结点。在遍历结点的时候，直接先将出度为0的安全状态结点找出来，排入一个队列queue中，方便后续的处理。后续的处理就有些类似BFS的操作了，我们循环非空queue，取出队首元素，标记safe中该结点为安全状态结点，然后遍历其逆向边的结点，即可以到达当前队首结点的所有结点，我们在正向边集合中删除对应的边，如果此时结点出度为0了，将其加入队列queue中等待下一步处理，这样while循环退出后，所有的安全状态结点都已经标记好了，我们直接遍历safe数组，将其存入结果res中即可，

class Solution {
public:
	vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
		int n = graph.size();
		vector<bool> safe(n, false);
		vector<set<int>> g(n,set<int>()), revg = g;
		queue<int> q;//存储入度为0的节点
		vector<int> ans;//结果
		for (int i = 0; i < n; i++)
		{
			if (graph[i].empty())
			{
				q.push(i);
			}
			for (int j : graph[i])
			{
				g[i].insert(j);//创建正向图
				revg[j].insert(i);//创建反向图
			}
		}
		while (!q.empty())
		{
			int t = q.front();//当前的安全节点
			q.pop();
			safe[t] = true;
			for (int i : revg[t])
			{
				g[i].erase(t);
				if (g[i].empty())
					q.push(i);
			}
		}
		for (int i = 0; i < n; i++)
		{
			if (safe[i])
				ans.push_back(i);
		}
		return ans;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

方法二：再来看一种DFS遍历有向图的解法。仔细分析题目中的例子，不难发现，之所以某些结点不是安全状态，因为有环的存在，而环经过的所有结点，一定不是安全状态结点，所以我们可以通过DFS遍历有向图来找出环即可。在大多数的算法中，经典的DFS遍历法对于结点都有三种状态标记，white，gray，和black，其中white表示结点还未遍历，gray表示正在遍历邻结点，black表示已经结束该结点的遍历。那么我们可以对每个结点都调用递归函数，在递归函数中，如果当前结点不是white，表示该结点已经访问过了，那么如果当前结点是black，直接返回true，如果是gray，直接返回false，因为遇到gray的结点，表示一定有环存在。否则我们给结点标记gray，然后开始遍历所有邻接结点，如果某个邻结点是black，直接跳过该结点。如果某个邻结点是gray，或者对该邻结点调用递归返回false了，说明当前结点是环结点，返回false。如果循环结束了，当前结点标记为black，并且返回true

class Solution {
public:
	vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
		vector<int> ans;
		int n = graph.size();
		vector<int> color(n);
		for (int i = 0; i < n; i++)
		{
			if (helper(graph,i,color)) ans.push_back(i);
		}
		return ans;
	}

	bool helper(vector<vector<int>>& graph, int node, vector<int>& color)
	{
		if (color[node] > 0) return color[node] == 2;//如果已经有标记
		color[node] = 1;//访问过的记为灰色
		for (int i : graph[node])//遍历下一个节点
		{
			if (color[i] == 2) continue;//如果是黑色，继续下一个节点
			if (color[i] == 1 || !helper(graph, i, color))//这个节点访问过或者不是安全节点
				return false;
		}
		color[node] = 2;//是安全节点
		return true;
	}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

两种方法的时间复杂度均为O(N+E)，空间复杂度均为O(N)。但是方法一新建了数据结构存储图和逆向图，再对两个图做处理，所占空间更大，耗时更久。