###### tags: `Leetcode` `medium` `graph` `topological sort` `python` `c++`

# 802. Find Eventual Safe States

## [題目連結:] https://leetcode.com/problems/find-eventual-safe-states/description/

## 題目:
There is a directed graph of ```n``` nodes with each node labeled from ```0``` to ```n - 1```. The graph is represented by a **0-indexed** 2D integer array ```graph``` where ```graph[i]``` is an integer array of nodes adjacent to node i, meaning there is an edge from node ```i``` to each node in ```graph[i]```.

A node is a **terminal node** if there are no outgoing edges. A node is a **safe node** if every possible path starting from that node leads to a **terminal node** (or another safe node).

Return an array containing all the **safe nodes** of the graph. The answer should be sorted in **ascending** order.


## 解題想法:
* 此題為:
* terminal node: outdegrees=0的點
* safe node為，可由此點到達terminal node
* 說明:
* 此題題目有點複雜，其實簡單而言就是
* **Step1**: 每次紀錄outdegree=0的node於res
* **Step2**: 刪除該點，並將其連到此點的邊都刪除
* loop Step1、Step2 until no more node outdegree=0
* 流程:
* Step1:建立邊

	for pos,val in enumerate(graph):
		for node in val:
			#要反向連
			edges[node].append(pos) #注意!
			outdegrees[pos]+=1 #自己 
			indegrees[node]+=1 #對方

* ex: graph=[[1,2]], 0->1 and 0->2
* outdegrees[0]+=1
* indegrees[1]+=1、indegrees[2]+=1
* **技巧:** 正常來說應該要是edges[pos].append(pos)
* **但是為了知道有誰連到terminal**，所以將邊線**反向連**
* 否則下面進行while時:
* 若用edges[pos].append(pos)，由於que中的curNode本身就沒連人了，根本檢測不了
* Step2: que紀錄outdegrees==0的node

	res=[]
	que=[]
	for pos,val in enumerate(outdegrees):
		if val==0:
			que.append(pos)

* Step3: 刪掉連線，重複尋找
* 是鄰居的outdegree要-1，因為鄰居連到curNode

	while que:
            curNode=que.pop(0)
            res.append(curNode)
            for neighber in edges[curNode]:
                outdegrees[neighber]-=1
                if outdegrees[neighber]==0:
                    que.append(neighber)

* 網上看有大神用DFS解題，等二刷再研究ㄌ~
## Python:

from collections import defaultdict
class Solution(object):
    def eventualSafeNodes(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: List[int]
        """
        edges=defaultdict(list)
        indegrees=[0]*len(graph)
        outdegrees=[0]*len(graph)
        for pos,val in enumerate(graph):
            for node in val:
                #ex: graph=[[1,2]], 0->1 and 0->2
                #正常來說應該是edges[pos].append(pos)
                #但是為了知道有誰連到terminal，所以將邊線反向連
                #否則下面進行while時:
                #若用edges[pos].append(pos)，由於que中的curNode本身就沒連人了，根本檢測不了
                edges[node].append(pos) 
                outdegrees[pos]+=1 #自己 
                indegrees[node]+=1 #對方
        res=[]
        que=[]
        for pos,val in enumerate(outdegrees):
            if val==0:
                que.append(pos)
        while que:
            curNode=que.pop(0)
            res.append(curNode)
            for neighber in edges[curNode]:
                outdegrees[neighber]-=1
                if outdegrees[neighber]==0:
                    que.append(neighber)
        res.sort()
        return res

## C++:

class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        unordered_map<int,vector<int>> edges;
        int n=graph.size();
        vector<int> outdegrees(n,0), indegrees(n,0);
        //connect the graph
        for (int i=0; i<n; i++){
            for (auto val: graph[i]){
                edges[val].push_back(i); //反向連
                outdegrees[i]+=1;
                indegrees[val]+=1;
            }
        }
        vector<int> res;
        queue<int> que;
        for (int i=0; i<n; i++){
            if (outdegrees[i]==0)
                que.push(i);
        }
        //collect the node which outdegrees==0
        while (!que.empty()){
            int curNode=que.front(); que.pop();
            res.push_back(curNode);
            for (auto neighber: edges[curNode]){
                outdegrees[neighber]-=1;
                if (outdegrees[neighber]==0)
                    que.push(neighber);
            }
        }
        sort(res.begin(), res.end());
        return res;
    }
};