leetcode547省份数量-526互联

深度优先搜索

vector<bool>vis;
int num=0;
void dfs(vector<vector<int>>& isConnected,int x){
  vis[x]=true;
  for(int i=0;i<isConnected[x].size();i++){
        if(!vis[i]&&isConnected[x][i]){
           dfs(isConnected,i);    
        }
      }    
}
int main(){
  int n=isConnected.size();
  vis.resize(n) ;
  for(int i=0;i<n;i++){
     if(!vis[i]){
         dfs(isConnected,i);
          num++;     
      } 
  }     
}

广度优先搜索

vector<bool>vis;
    int num=0;
    queue<int>q;
    void bfs(vector<vector<int>>& isConnected,int x){
        q.push(x);
       while(!q.empty()){
           int x=q.front();q.pop();
           for(int i=0;i<isConnected[x].size();i++){
               if(!vis[i]&&isConnected[x][i]){
                   q.push(i);
                   vis[i]=true;
               }
           }
       } 
    }