leetcode

0 class Solution {

1 public:

2 vector<int> eventualSafeNodes(const vector<vector<int>> &graph) {

3 int n = graph.size();

4 vector<bool> visited(n, false), safe(n, false);

5 stack<int> st;

6 for (int i = 0; i < n; i++) {

7 if (visited[i]) continue;

8 st.push(i);

9 while (!st.empty()) {

10 int root = st.top();

11 if (root == -1) {

12 st.pop();

13 root = st.top();

14 st.pop();

15 bool s = true;

16 for (int c : graph[root])

17 if (!safe[c]) {

18 s = false;

19 break;

20 }

21 safe[root] = s;

22 continue;

23 }

24 if (visited[root]) {

25 st.pop();

26 continue;

27 };

28 visited[root] = true;

29 st.push(-1);

30 for (int c : graph[root])

31 if (!visited[c]) st.push(c);

32 }

33 }

34 vector<int> res;

35 for (int i = 0; i < n; i++)

36 if (safe[i]) res.push_back(i);

37 return res;

38 }

39 };

40

41 // Cleaner code, more memory

42 class Solution {

43 int safe[100001] = {0}, count[10001] = {0};

44

45 public:

46 vector<int> eventualSafeNodes(const vector<vector<int>> &graph) {

47 int n = graph.size();

48 vector<vector<int>> adj(n);

49 for (int i = 0; i < n; i++) {

50 count[i] += graph[i].size();

51 for (int node : graph[i])

52 adj[node].push_back(i);

53 }

54

55 queue<int> q;

56 for (int i = 0; i < n; i++)

57 if (!count[i]) q.push(i);

58

59 while (!q.empty()) {

60 int root = q.front();

61 q.pop();

62 safe[root] = true;

63

64 for (auto node : adj[root])

65 if (!--count[node]) q.push(node);

66 }

67

68 vector<int> res;

69 for (int i = 0; i < graph.size(); i++)

70 if (safe[i]) res.push_back(i);

71 return res;

72 }

73 };