# Simple C++ DFS Using Graph Coloring

• 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 {
public:
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[]
book=init;
for(int i=0;i<row;i++){//use dfs on any point of '1'
for(int j=0;j<col;j++){
if(grid[i][j]=='1'){
color--;
book[i][j]=1;//now the point has been visited, mark it
dfs(grid,i,j,color);
}
}
}
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
continue;
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
}
}
}
};
``````

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