Simple C++ DFS Using Graph Coloring

  • 0

    The idea is based on graph coloring, we use different colors to color the same island, the number of islands = the number of colors we use.
    The code is as follow:

    class Solution {
        vector<vector<int>> book;//mark if a point has been visited or not,it's global
        int numIslands(vector<vector<char>>& grid) {
            int color=0;//use number from -1 to -n to color the graph, initially set it to be 0
            int row=grid.size();
            if(row==0)return 0;
            int col=grid[0].size();
            vector<vector<int>> init(row,vector<int>(col,0));//use it to initialize book[]
            for(int i=0;i<row;i++){//use dfs on any point of '1'
                for(int j=0;j<col;j++){
                        book[i][j]=1;//now the point has been visited, mark it
            return -color;//each island needs a color, number of islands = number of colors = -color(since it starts from 0)
        void dfs(vector<vector<char>>& grid,int x,int y,int color){
            int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//different directions
            int row=grid.size();
            int col=grid[0].size();
            grid[x][y]=color;//color the current point
            for(int k=0;k<4;k++){//try 4 different directions
                int tx=x+next[k][0];
                int ty=y+next[k][1];
                if(tx<0||tx>row-1||ty<0||ty>col-1)//the border
                if(grid[tx][ty]=='1'&&book[tx][ty]==0){//if it's '1' and hasn't been visited yet
                    book[tx][ty]=1;//visit it
                    dfs(grid,tx,ty,color);//continue to search

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.