DAY14 - 拓扑排序

今天要写拓扑排序~~
一个有向无环图，必定存在一种(以上)的拓扑排序
定义：
将图中所有点展开成序列，对任意节点u, v而言，若u出现在v的前面，说明图中有u->v的通路
一样找一题例题来解释~~

例题&算法

802. 找到最终的安全状态
题目叙述：题目给一张图，输出有哪些起点，最後可以在有限步数走到终点(也就是无环)

[法一]拓扑排序

思路：

1. 先绘制一张反图(方向相反)
2. 找出反图入度为0的节点(原本图的出度0)，这些节点是安全的(走到这一定无环了，因为原本的图这些节点出度0，也就是终点)
3. 将这些节点放入queue中
4. 取出queue元素，与queue中节点相邻的节点入度减一
5. 重复2->3->4
   最後入度为0的，都是安全的节点
   直接看程序码~~

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        //反图&inDeg
        int n = graph.size();
        vt<int> inDeg(n);
        vt<int> res;
        iMat rg(n);
        for(int i = 0; i<n; ++i){
            inDeg[i] = graph[i].size();
            for(int j = 0; j<graph[i].size(); ++j){
                rg[graph[i][j]].pb(i);
            }
        }
        queue<int> q;
        //将所有入度=0的放入queue
        for(int i = 0; i<n; ++i){
            if(inDeg[i]==0){
                q.push(i);
            }
        }
        while(!q.empty()){
            int curr = q.front();
            q.pop();
            vt<int> adj = rg[curr];
            for(int i = 0; i<adj.size(); ++i){
                inDeg[adj[i]]--;
                if(inDeg[adj[i]]==0){
                    q.push(adj[i]);
                }
            }
        }
        for(int i = 0; i<n; ++i){
            if(inDeg[i]==0){
                res.pb(i);
            }
        }
        return res;
    }
};

WHY?

反图入度为0(原本的图出度0)就代表这个节点是终点了，一定没有办法形成环，那走到这个节点的路一定也不会形成环，可以将这条边去除(相邻节点反图入度-1)，最後入度为0的全部都是安全节点~~

[法二]标注DFS

就是DFS加上标注
标注出3种状态

1. 未访问
2. 访问中
3. 已访问(安全)

#define vt vector
#define pb push_back
#define iipair pair<int, int>
#define cipair pair<char, int>
#define icpair pair<int, char>
#define ispair pair<int, string>
#define sipair pair<string, int>
#define MOD 1e9+7
#define iMat vector<vector<int>>
#define cMat vector<vector<char>>
#define ll long long
#define mp make_pair
class Solution {
    vt<int> mark;
public:
    vector<int> eventualSafeNodes(vector<vector<int>>& graph) {
        //[法一] 3种状态DFS，可以算是记忆化搜索(?
        int n = graph.size();
        mark.resize(n);
        vt<int> res;
        for(auto& i:mark){
            mark[i] = 0; //未被访问
        }
        for(int i = 0; i<n; ++i){
            if(dfs(graph, i)){
                res.pb(i);
            }
        }
        return res;
    }
    bool dfs(iMat& graph, int node){
        if(mark[node]!=0){
            return mark[node]==2;
        }
        vt<int> adj = graph[node];
        mark[node] = 1;
        for(auto e:adj){
            if(!dfs(graph, e)){
                return false;
            }
        }
        mark[node] = 2;
        return true;
    }
};