题解 | #城市群数量#

class Solution {
public:
    int citys(vector<vector<int> >& m) {
        int n = m.size();//城市数量
        int count = 0;
        queue<int> que;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                //if(i==j){m[i][j] = 0; } //独立的城市也算一个城市群
                if(m[i][j]==1){
                    count++;
                    que.push(i);
                    while(!que.empty()){//将所有与i相连的点去掉
                        auto tmp = que.front();
                        que.pop();
                        for(int p=0; p<n; p++){
                            if(tmp==p){
                                m[tmp][p]=0;
                            } 
                            if(m[tmp][p]==1){
                                que.push(p);
                                m[tmp][p] = 0;
                                m[p][tmp] = 0;//不加也可以，加了就不会往回走
                            }
                        }
                    }
                }
            }
        }
        return count;
    }
};

bfs广度优先，要画图才有利于理解。