FilesExpand file tree

 master

/

FindEventualSafeStates802.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

90 lines (79 loc) · 2.88 KB

 master

/

FindEventualSafeStates802.java

Copy path

Top

File metadata and controls

• Code
• Blame

90 lines (79 loc) · 2.88 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

/**

* In a directed graph, we start at some node and every turn, walk along a

* directed edge of the graph. If we reach a node that is terminal (that is,

* it has no outgoing directed edges), we stop.

*

* Now, say our starting node is eventually safe if and only if we must

* eventually walk to a terminal node. More specifically, there exists a

* natural number K so that for any choice of where to walk, we must have

* stopped at a terminal node in less than K steps.

*

* Which nodes are eventually safe? Return them as an array in sorted order.

*

* The directed graph has N nodes with labels 0, 1, ..., N-1, where N is the

* length of graph. The graph is given in the following form: graph[i] is a

* list of labels j such that (i, j) is a directed edge of the graph.

*

* Example:

* Input: graph = [[1,2],[2,3],[5],[0],[5],[],[]]

* Output: [2,4,5,6]

*

* Here is a diagram of the above graph.

* https://s3-lc-upload.s3.amazonaws.com/uploads/2018/03/17/picture1.png

*

* Note:

* graph will have length at most 10000.

* The number of edges in the graph will not exceed 32000.

* Each graph[i] will be a sorted list of different integers, chosen within

* the range [0, graph.length - 1].

*/

public class FindEventualSafeStates802 {

public List<Integer> eventualSafeNodes(int[][] graph) {

List<Integer> res = new ArrayList<>();

if (graph == null || graph.length == 0) return res;

int N = graph.length;

boolean[] saved = new boolean[N];

boolean[] visited = new boolean[N];

for (int i=0; i<N; i++) {

if (checkTermial(graph, i, visited, saved)) res.add(i);

}

return res;

}

private boolean checkTermial(int[][] graph, int now, boolean[] visited, boolean[] saved) {

if (saved[now]) return true;

if (visited[now]) return false;

visited[now] = true;

for (int next: graph[now]) {

if (!checkTermial(graph, next, visited, saved)) return false;

}

visited[now] = false;

saved[now] = true;

return true;

}

/**

* https://leetcode.com/problems/find-eventual-safe-states/solution/

*/

public List<Integer> eventualSafeNodes2(int[][] graph) {

int N = graph.length;

int[] color = new int[N];

List<Integer> ans = new ArrayList();

for (int i = 0; i < N; ++i)

if (dfs(i, color, graph))

ans.add(i);

return ans;

}

// colors: WHITE 0, GRAY 1, BLACK 2;

public boolean dfs(int node, int[] color, int[][] graph) {

if (color[node] > 0)

return color[node] == 2;

color[node] = 1;

for (int nei: graph[node]) {

if (color[node] == 2)

continue;

if (color[nei] == 1 || !dfs(nei, color, graph))

return false;

}

color[node] = 2;

return true;

}

}