算法15--BFS

有一幅以 m x n 的二维整数数组表示的图画 image ，其中 image[i][j] 表示该图画的像素值大小。你也被给予三个整数 sr , sc 和 color 。你应该从像素 image[sr][sc] 开始对图像进行上色 填充 。
为了完成 上色工作：
从初始像素开始，将其颜色改为 color。
对初始坐标的 上下左右四个方向上 相邻且与初始像素的原始颜色同色的像素点执行相同操作。
通过检查与初始像素的原始颜色相同的相邻像素并修改其颜色来继续 重复 此过程。
当 没有 其它原始颜色的相邻像素时 停止 操作。
最后返回经过上色渲染 修改 后的图像 。

class Solution {
public:
    
    void GetAnswer(vector<vector<int>>& image, int sr, int sc, int color,int originColor){
        if(sr<0||sc<0||sr>=image.size()||sc>=image[0].size()||originColor!=image[sr][sc]){
            return;
        }
        image[sr][sc]=color;
        printf("%d %d\n",sr,sc);
        GetAnswer(image,sr-1,sc,color,originColor);
        GetAnswer(image,sr+1,sc,color,originColor);
        GetAnswer(image,sr,sc-1,color,originColor);
        GetAnswer(image,sr,sc+1,color,originColor);
    }
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        if(color!=image[sr][sc]){
            GetAnswer(image,sr,sc,color,image[sr][sc]);
        }
        return image;
    }
};

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。

class Solution {
public:
    void Cover(vector<vector<char>>& grid,vector<vector<char>>& record,int i,int j){
        if(i<0||j<0||i>=grid.size()||j>=grid[0].size()||'0'==record[i][j]||'0'==grid[i][j]){
            return;
        }
        record[i][j]='0';
        Cover(grid,record,i+1,j);
        Cover(grid,record,i-1,j);
        Cover(grid,record,i,j+1);
        Cover(grid,record,i,j-1);
    }
    int numIslands(vector<vector<char>>& grid) {
        vector<vector<char>> record(grid.size(),vector<char>(grid[0].size(),'1'));
        int i=0;
        int ans=0;
        for(i=0;i<grid.size();++i){
            int j=0;
            for(j=0;j<grid[0].size();++j){
                if('1'==grid[i][j]&&'1'==record[i][j]){
                    ++ans;
                    Cover(grid,record,i,j);
                }
            }
        }

        return ans;
    }
};

给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

class Solution {
public:
    int GetArea(vector<vector<int>>& grid,vector<vector<int>>& copyGrid,int row,int column){
        if(row<0||row>=grid.size()
        ||column<0||column>=grid[0].size()
        ||0==copyGrid[row][column]||0==grid[row][column]){
            return 0;
        }

        copyGrid[row][column]=0;
        int left=GetArea(grid,copyGrid,row,column-1);
        int right=GetArea(grid,copyGrid,row,column+1);
        int up=GetArea(grid,copyGrid,row-1,column);
        int down=GetArea(grid,copyGrid,row+1,column);
        return left+right+up+down+1;
    }
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        vector<vector<int>> copyGrid(grid.size(),vector<int>(grid[0].size(),1));
        int maxArea=0;
        int i=0;
        for(;i<grid.size();++i){
            int j=0;
            for(;j<grid[0].size();++j){
                maxArea=max(maxArea,GetArea(grid,copyGrid,i,j));
            }
        }

        return maxArea;
    }
};

给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ 组成，捕获 所有 被围绕的区域：
连接：一个单元格与水平或垂直方向上相邻的单元格连接。
区域：连接所有 ‘O’ 的单元格来形成一个区域。
围绕：如果您可以用 ‘X’ 单元格 连接这个区域，并且区域中没有任何单元格位于 board 边缘，则该区域被 ‘X’ 单元格围绕。
通过 原地 将输入矩阵中的所有 ‘O’ 替换为 ‘X’ 来 捕获被围绕的区域。你不需要返回任何值。

class Solution {
public:
    bool IsSurround(vector<vector<char>>& board,vector<vector<int>>& copyBoard,int i,int j){
        if(0==copyBoard[i][j]){
            return true;
        }
        if('X'==board[i][j]
        ||i==0||j==0||i+1==board.size()||j+1==board[0].size()){

            copyBoard[i][j]=0;
            if('X'==board[i][j]){
                return true;
            }
            return false;
        }
        copyBoard[i][j]=0;
        int left=IsSurround(board,copyBoard,i,j-1);
        int right=IsSurround(board,copyBoard,i,j+1);
        int up=IsSurround(board,copyBoard,i-1,j);
        int down=IsSurround(board,copyBoard,i+1,j);

        return left&&right&&up&&down;
    }

    void Replace(vector<vector<char>>& board,int i,int j){
        if('X'==board[i][j]){
            return;
        }
        board[i][j]='X';
        Replace(board,i-1,j);
        Replace(board,i+1,j);
        Replace(board,i,j-1);
        Replace(board,i,j+1);
    }

    void solve(vector<vector<char>>& board) {
        vector<vector<int>> copyBoard(board.size(),vector<int>(board[0].size(),1));
        int i=1;
        for(;i+1<board.size();++i){
            int j=1;
            for(;j+1<board[0].size();++j){
                if('O'==board[i][j]&&1==copyBoard[i][j]&&IsSurround(board,copyBoard,i,j)){
                    Replace(board,i,j);
                }
            }
        }
    }
};

给你一个 m x n 的迷宫矩阵 maze （下标从 0 开始），矩阵中有空格子（用 ‘.’ 表示）和墙（用 ‘+’ 表示）。同时给你迷宫的入口 entrance ，用 entrance = [entrancerow, entrancecol] 表示你一开始所在格子的行和列。
每一步操作，你可以往 上，下，左 或者 右 移动一个格子。你不能进入墙所在的格子，你也不能离开迷宫。你的目标是找到离 entrance 最近 的出口。出口 的含义是 maze 边界 上的 空格子。entrance 格子 不算 出口。
请你返回从 entrance 到最近出口的最短路径的 步数 ，如果不存在这样的路径，请你返回 -1 。

class Solution {
public:
    bool Renew(vector<vector<char>>& maze,vector<vector<int>>& record,queue<vector<int>> &q,int i,int j,int& cur){
        if (0 > i || 0 > j || i == maze.size() || j == maze[0].size() || '+' == maze[i][j] || 0 == record[i][j]) {
            return false;
        }
        if(0 == i || 0 == j || i+1 == maze.size() || j+1 == maze[0].size()){
            return true;
        }
        record[i][j]=0;
        q.push({i,j});
        ++cur;
        return false;
    }

    int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {
        vector<vector<int>> record(maze.size(),vector<int>(maze[0].size(),1));
        record[entrance[0]][entrance[1]]=0;
        queue<vector<int>> q;
        q.push(entrance);
        int d=1;
        int count=1;
        while(!q.empty()){
            int cur=0;
            while(count--){
                int i=q.front()[0];
                int j=q.front()[1];
                q.pop();
                int left=Renew(maze,record,q,i,j-1,cur);
                int right=Renew(maze,record,q,i,j+1,cur);
                int up=Renew(maze,record,q,i-1,j,cur);
                int down=Renew(maze,record,q,i+1,j,cur);
                if(left||right||up||down){
                    return d;
                }
            }
            count=cur;
            ++d;
        }

        return -1;
    }
};

基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 ‘A’、‘C’、‘G’ 和 ‘T’ 之一。
假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。
例如，“AACCGGTT” --> “AACCGGTA” 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）
给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。
注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

class Solution {
public:
    void SToI(map<char,int>& mapOfCToI,string& s,vector<int>& res){
            int i=0;
            for(;i<8;++i){
                res.push_back(mapOfCToI[s[i]]);
            }
    }

    bool IsLegal(map<vector<int>,int>& mp,vector<int>& v){
        int i=0;
        for(;i<8;++i){
            auto it=mp.find(v);
            if(v[i]<0||v[i]==8||mp.end()==it||it->second==0){
                return false;
            }
        }

        return true;
    }

    int minMutation(string startGene, string endGene, vector<string>& bank) {
        map<char,int> mapOfCToI;
        mapOfCToI['A']=0;
        mapOfCToI['C']=1;
        mapOfCToI['G']=2;
        mapOfCToI['T']=3;
        map<vector<int>,int> mp;
        for(auto& e:bank){
            vector<int> res;
            SToI(mapOfCToI,e,res);
            mp[res]=1;
        }

        vector<int> start;
        vector<int> end;
        queue<vector<int>> q;
        int count=1;
        int d=1;

        SToI(mapOfCToI,startGene,start);
        SToI(mapOfCToI,endGene,end);
        q.push(start);
        mp[start]=0;
        if(mp.end()==mp.find(end)){
            return -1;
        }


        while(!q.empty()){
            int cur=0;
            while(count--){
                vector<int> tmp=q.front();
                q.pop();
                int i=0;
                for(;i<8;++i){
                    int j=0;
                    int k=tmp[i];
                    for(;j<4;++j){
                        tmp[i]=j;
                        if(IsLegal(mp,tmp)){
                            q.push(tmp);
                            mp[tmp]=0;
                            ++cur;
                            if(0==mp[end]){
                                return d;
                            }
                        }
                    }
                    tmp[i]=k;
                }
            }
            ++d;
            count=cur;
        }

        return -1;
    }
};

字典 wordList 中从单词 beginWord 到 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        if(beginWord.size()!=endWord.size()){
            return 0;
        }
        wordList.push_back(beginWord);
        map<string, int> mp;
        for (auto& e : wordList) {
            if(e.size()==beginWord.size()){
                mp[e]=1;
            }
        }
        if(mp.end()==mp.find(endWord)){
            return 0;
        }
        queue<string> q;
        q.push(beginWord);
        mp[beginWord]=0;
        int count = 1;
        int d = 2;

        while (!q.empty()) {
            int cur = 0;
            while (count--) {
                string tmp = q.front();
                q.pop();
                int i = 0;
                for (; i < beginWord.size(); ++i) {
                    int j = 0;
                    char c = tmp[i];
                    for (; j < 26; ++j) {
                        tmp[i] = 'a'+j;
                        auto it=mp.find(tmp);
                        if (mp.end()!=it&&it->second) {
                            q.push(tmp);
                            it->second = 0;
                            ++cur;
                            if (0 == mp[endWord]) {
                                return d;
                            }
                        }
                    }
                    tmp[i] = c;
                }
            }
            ++d;
            count = cur;
        }

        return 0;
    }
};

你被请来给一个要举办高尔夫比赛的树林砍树。树林由一个 m x n 的矩阵表示， 在这个矩阵中：
0 表示障碍，无法触碰
1 表示地面，可以行走
比 1 大的数 表示有树的单元格，可以行走，数值表示树的高度
每一步，你都可以向上、下、左、右四个方向之一移动一个单位，如果你站的地方有一棵树，那么你可以决定是否要砍倒它。
你需要按照树的高度从低向高砍掉所有的树，每砍过一颗树，该单元格的值变为 1（即变为地面）。
你将从 (0, 0) 点开始工作，返回你砍完所有树需要走的最小步数。 如果你无法砍完所有的树，返回 -1 。
可以保证的是，没有两棵树的高度是相同的，并且你至少需要砍倒一棵树。

class Solution {
public:
    bool record[51][51];
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int GetDist(vector<vector<int>>& forest,vector<int>& src,vector<int>& dest){
        if(src[0]==dest[0]&&src[1]==dest[1]){
            return 0;
        }
        memset(record,1,sizeof(record));
        int dist=1;
        queue<pair<int, int>> cordiates;
        cordiates.push({src[0],src[1]});
        record[src[0]][src[1]]=0;
        while(!cordiates.empty()){
            int count=cordiates.size();
            while(count--){
                auto tmp=cordiates.front();
                cordiates.pop();
                int k=4;
                while(k--){
                    int i=tmp.first+dx[k];
                    int j=tmp.second+dy[k];
                    if(i>=0&&i<forest.size()&&j>=0&&j<forest[0].size()&&forest[i][j]&&record[i][j]){
                        if(i==dest[0]&&j==dest[1]){
                            return dist;
                        }
                        cordiates.push({i,j});
                        record[i][j]=0;
                    }
                }
            }
            ++dist;
        }

        return -1;
    }

    int cutOffTree(vector<vector<int>>& forest) {
        if(0==forest[0][0]){
            return -1;
        }
        vector<vector<int>> cordiates;
        int i=0;
        int j=0;
        for(i=0;i<forest.size();++i){
            for(j=0;j<forest[0].size();++j){
                if(forest[i][j]>1){
                    cordiates.push_back({i,j});
                }
            }
        }
        sort(cordiates.begin(),cordiates.end(),[&](vector<int>& v1,vector<int>& v2)->bool{
            return forest[v1[0]][v1[1]]<forest[v2[0]][v2[1]];
        });

        int dist=0;
        vector<int> src={0,0};
        vector<int>& dest=cordiates[0];
        for(i=0;i<cordiates.size();++i){
            dest=cordiates[i];
            int t=GetDist(forest,src,dest);
            //int t=bfs(forest,src[0],src[1],dest[0],dest[1]);
            if(t<0){
                return -1;
            }
            src=dest;
            dist+=t;
        }

        return dist;
    }
};

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。

以所有值为0的点作为起点，值为1的点作为终点执行BFS算法即可

class Solution {
public:
    bool IsLegal(vector<vector<int>>& ans,vector<int>& cordiate){
        if(cordiate[0]<0||cordiate[1]<0
        ||cordiate[0]>=ans.size()||cordiate[1]>=ans[0].size()
        ||ans[cordiate[0]][cordiate[1]]>=0){
            return false;
        }

        return true;
    }

    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        vector<vector<int>> ans(mat.size(),vector<int>(mat[0].size(),-1));
        int dist=1;
        queue<vector<int>> q;
        int i=0;
        for(;i<mat.size();++i){
            int j=0;
            for(;j<mat[0].size();++j){
                if(0==mat[i][j]){
                    q.push({i,j});
                    ans[i][j]=0;
                }
            }
        }
        int count=q.size();
        while(!q.empty()){
            int cur=0;
            while(count--){
                auto tmp=q.front();
                q.pop();
                vector<vector<int>> cordiates;
                cordiates.push_back({tmp[0]+1,tmp[1]});
                cordiates.push_back({tmp[0]-1,tmp[1]});
                cordiates.push_back({tmp[0],tmp[1]+1});
                cordiates.push_back({tmp[0],tmp[1]-1});
                int k=0;
                for(;k<4;++k){
                    if(IsLegal(ans,cordiates[k])){
                        ans[cordiates[k][0]][cordiates[k][1]]=dist;
                        q.push(cordiates[k]);
                        ++cur;
                    }
                }
            }
            count=cur;
            ++dist;
        }

        return ans;
    }
};

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

以所有值为1的边界点作为起点执行BFS，将离开网格边界的陆地单元格置为0，最后值仍为1的点就是网格中 无法 在任意次数的移动中离开网格边界的陆地单元格。

class Solution {
public:
    int Renew(vector<vector<int>>& grid,int i,int j){
        if(i<0||j<0||i>=grid.size()||j>=grid[0].size()||0==grid[i][j]){
            return 0;
        }
        grid[i][j]=0;
        int left=Renew(grid,i,j-1);
        int right=Renew(grid,i,j+1);
        int up=Renew(grid,i-1,j);
        int down=Renew(grid,i+1,j);

        return left+right+up+down+1;
    }
    int numEnclaves(vector<vector<int>>& grid) {
        int ans=0;
        int i=0;
        int j=0;
        vector<vector<int>>  cordiates;
        for(i=0;i<grid.size();++i){
            for(j=0;j<grid[0].size();++j){
                if(1==grid[i][j]){
                    if(i==0||j==0||i+1==grid.size()||j+1==grid[0].size()){
                        cordiates.push_back({i,j});
                    }
                    ++ans;
                }
            }
        }
        for(auto & e:cordiates){
            ans-=Renew(grid,e[0],e[1]);
        }

        return ans;
    }
};

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。
如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。
如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。
你需要按照如下规则给每个单元格安排高度：
每个格子的高度都必须是非负的。
如果一个格子是 水域 ，那么它的高度必须为 0 。
任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）
找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。
请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

class Solution {
public:
    void Renew(vector<vector<int>>& isWater,vector<vector<int>>& ans,queue<vector<int>>& q,int & cur,int dist,int i, int j) {
        if (i < 0 || j < 0 || i >= isWater.size() || j >= isWater[0].size() || 1 == isWater[i][j]) {
            return;
        }
        isWater[i][j] = 1;
        ans[i][j]=dist;
        q.push({i,j});
        ++cur;
    }

    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int i=0;
        int j=0;
        int dist=1;
        vector<vector<int>> ans(isWater.size(),vector<int>(isWater[0].size(),0));
        queue<vector<int>> q;
        for(i=0;i<isWater.size();++i){
            for(j=0;j<isWater[0].size();++j){
                if(1==isWater[i][j]){
                    q.push({i,j});
                }
            }
        }
        int count=q.size();
        while(!q.empty()){
            int cur=0;
            while(count--){
                auto e=q.front();
                q.pop();
                Renew(isWater,ans,q,cur,dist,e[0]+1,e[1]);
                Renew(isWater,ans,q,cur,dist,e[0]-1,e[1]);
                Renew(isWater,ans,q,cur,dist,e[0],e[1]+1);
                Renew(isWater,ans,q,cur,dist,e[0],e[1]-1);
            }
            ++dist;
            count=cur;
        }

        return ans;
    }
};

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。
请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。
、我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

class Solution {
public:
    void Renew(vector<vector<int>>& grid,queue<vector<int>> &q,int& cur,int i,int j){
        if(i<0||j<0||i==grid.size()||j==grid[0].size()||1==grid[i][j]){
            return ;
        }
        q.push({i,j});
        grid[i][j]=1;
        ++cur;
    }

    int maxDistance(vector<vector<int>>& grid) {
        queue<vector<int>> q;
        int i=0;
        int j=0;
        for(i=0;i<grid.size();++i){
            for(j=0;j<grid[0].size();++j){
                if(1==grid[i][j]){
                    q.push({i,j});
                }
            }
        }
        if(q.empty()||grid.size()*grid[0].size()==q.size()){
            return -1;
        }
        int count=q.size();
        int dist=-1;
        while(!q.empty()){
            int cur=0;
            while(count--){
                auto e=q.front();
                q.pop();
                Renew(grid,q,cur,e[0]+1,e[1]);
                Renew(grid,q,cur,e[0]-1,e[1]);
                Renew(grid,q,cur,e[0],e[1]+1);
                Renew(grid,q,cur,e[0],e[1]-1);
            }
            count=cur;
            ++dist;
        }

        return dist;
    }
};

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> count(numCourses,0);

        //采用邻接表vector<vector<T>>建图
        vector<vector<int>> edges(numCourses,vector<int>());
        for(auto& e:prerequisites){
            edges[e[1]].push_back(e[0]);
            count[e[0]]++;
        }

        //BFS
        int m=0;
        queue<int> q;
        int i=0;
        for(i=0;i<count.size();++i){
            if(0==count[i]){
                q.push(i);
                ++m;
            }
        }
        while(!q.empty()){
            int s=q.size();
            while(s--){
                int course=q.front();
                q.pop();
                for(auto e:edges[course]){
                    count[e]--;
                    if(0==count[e]){
                        q.push(e);
                        ++m;
                    }
                }
            }
        }
        if(m<numCourses){
            return false;
        }

        return true;
    }
};

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前 必须 先选修 bi 。
例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<int> count(numCourses, 0);
        vector<int> ans;
        //采用邻接表vector<vector<T>>建图
        vector<vector<int>> edges(numCourses, vector<int>());
        for (auto& e : prerequisites) {
            edges[e[1]].push_back(e[0]);
            count[e[0]]++;
        }

        //BFS
        queue<int> q;
        int i = 0;
        for (i = 0; i < count.size(); ++i) {
            if (0 == count[i]) {
                q.push(i);
                ans.push_back(i);
            }
        }
        while (!q.empty()) {
            int s = q.size();
            while (s--) {
                int course = q.front();
                q.pop();
                for (auto e : edges[course]) {
                    count[e]--;
                    if (0 == count[e]) {
                        q.push(e);
                        ans.push_back(e);
                    }
                }
            }
        }
        if (ans.size() < numCourses) {
            return {};
        }

        return ans;
    }
};

现有一种使用英语字母的外星文语言，这门语言的字母顺序与英语顺序不同。
给定一个字符串列表 words ，作为这门语言的词典，words 中的字符串已经 按这门新语言的字母顺序进行了排序 。
请你根据该词典还原出此语言中已知的字母顺序，并 按字母递增顺序 排列。若不存在合法字母顺序，返回 “” 。若存在多种可能的合法字母顺序，返回其中 任意一种 顺序即可。
字符串 s 字典顺序小于 字符串 t 有两种情况：
在第一个不同字母处，如果 s 中的字母在这门外星语言的字母顺序中位于 t 中字母之前，那么 s 的字典顺序小于 t 。
如果前面 min(s.length, t.length) 字母都相同，那么 s.length < t.length 时，s 的字典顺序也小于 t 。

class Solution {
public:
    string alienOrder(vector<string>& words) {
        string ans;
        map<char,int> count;
        int i=0;
        int j=0;
        for(i=0;i<words.size();++i){
            for(j=0;j<words[i].size();++j){
                count[words[i][j]]=0;
            }
        }
        //采用哈希：map<T,vector<T>>建图
        map<char,set<char>> edges;
        for(i=1;i<words.size();++i){
            for(j=0;j<words[i].size()&&j<words[i-1].size();++j){
                if(words[i-1][j]!=words[i][j]){
                    if(edges[words[i-1][j]].end()==edges[words[i-1][j]].find(words[i][j])){
                        edges[words[i-1][j]].insert(words[i][j]);
                        count[words[i][j]]++;
                    }

                    break;
                }
            }
            if(j>=words[i].size()&&words[i-1].size()>words[i].size()){
                return "";
            }
        }

        //BFS
        queue<char> q;
        for(auto& e:count){
            if(0==e.second){
                q.push(e.first);
                ans.push_back(e.first);
            }
        }
        while(!q.empty()){
            int s=q.size();
            while(s--){
                char c=q.front();
                q.pop();
                for(auto e:edges[c]){
                    count[e]--;
                    if(0==count[e]){
                        q.push(e);
                        ans.push_back(e);
                    }
                }
            }
        }

        //判断是否有环
        for(auto& e:count){
            if(e.second){
                return "";
            }
        }

        return ans;
    }
};