刷完 TOP100 的二叉树速速来刷图，相比树最多有一个父节点和两个子节点，图可以拥有拥有更多相邻节点并根据图为有向图/无向图来界定有无子节点的概念（即有向图的一个节点指向另一节点而不能反向）

200. 岛屿数量

本题要找到是孤立的陆地（1），并且直接相连的 1 视为一块，所以用 dfs 把所有连着的 1 扫出来都改成 0，也即边界条件为i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0'

进行一个二维遍历，每新找到一块 1 就给 ans 加一即可。

class Solution {
public:
    void dfs(vector<vector<char>>& grid,int i,int j){
        int m=grid.size();
        int n=grid[0].size();

        if(i<0 || i>=m || j<0 || j>=n || grid[i][j]=='0'){
            return;
        }

        grid[i][j]='0';
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    }
    int numIslands(vector<vector<char>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        int ans=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]=='1'){
                    ans++;
                }
                dfs(grid,i,j);
            }
        }
        return ans;
    }
};

994. 腐烂的橘子

过完了上面的进度 DFS，接下来这题是经典 BFS，橘子烂一层给 time++即可

class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m=grid.size();
        int n=grid[0].size();
        queue<pair<int,int>> q;
        int fresh=0;

        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==2){
                    q.push({i,j});
                }
                if(grid[i][j]==1){
                    fresh++;
                }
            }
        }
        if(fresh==0) return 0;
        int time=0;
        int dx[4]={-1,1,0,0};
        int dy[4]={0,0,-1,1};
        while(!q.empty()){
            int size=q.size();
            bool changed=false;
            for(int i=0;i<size;i++){
                auto [x,y]=q.front();
                q.pop();
                for(int k=0;k<4;k++){
                    int nx=x+dx[k];
                    int ny=y+dy[k];
                    if(nx<0 || ny<0 || nx>=m || ny >=n){
                        continue;
                    }
                    if(grid[nx][ny]!=1) continue;
                    grid[nx][ny]=2;
                    fresh--;
                    q.push({nx,ny});
                    changed=true;
                }
            }
            if(changed) time++;
        }
        if(fresh>0) return -1;
        return time;
    }
};

207. 课程表

本题要求选 n 门课程，其中某些课程有前置课程要求，问能否选成 n 门课。

其实就是要求判断有向图中是否有环。

最经典的是 kahn 算法，走 BFS 的思路，先定义入度为课程有的先修课的数量，每完成一门课的时，以这门课为先修课的课程的入度就-1，当入度为 0 时加入完成队列，然后一层一层往下走即可

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> graph(numCourses);
        vector<int> indegree(numCourses,0);
        for(auto& p : prerequisites){
            int a=p[0];
            int b=p[1];
            graph[b].push_back(a);
            indegree[a]++;
        }
        queue<int> q;

        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                q.push(i);
            }
        }

        int count=0;
        while(!q.empty()){
            int course=q.front();
            q.pop();
            count++;
            for(int next: graph[course]){
                indegree[next]--;
                if(indegree[next]==0){
                    q.push(next);
                }
            }
        }
        return count==numCourses;
    }
};

208. 实现 Trie (前缀树)

这题为什么会放到图论里（？

第一次见前缀树这种数据结构，它把字符串拆成按树状一个一个串起来的字符，已经有的直接检索不反复存储，没有的按树状往下存。

代码其实不咋难写，就是一上来直接看到这种数据结构有点难理解（

class Trie {
private:
    Trie* children[26]={};
    bool isEnd=false;
public:
    Trie() {
        
    }
    
    void insert(string word) {
        Trie* node=this;
        for(char c: word){
            int index=c-'a';
            if(node->children[index]==nullptr){
                node->children[index]=new Trie();
            }
            node=node->children[index];
        }
        node->isEnd=true;
    }
    
    bool search(string word) {
        Trie* node=this;
        for(char c : word){
            int index=c-'a';
            if(node->children[index]==nullptr){
                return false;
            }
            node=node->children[index];
        }
        return node->isEnd;
    }
    
    bool startsWith(string prefix) {
        Trie* node=this;
        for(char c:prefix){
            int index=c-'a';
            if(node->children[index]==nullptr){
                return false;
            }
            node=node->children[index];
        }
        return true;
    }
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */