题解 | #城市群数量#

class Solution {
  public:
    void re(vector<vector<int> >& m, int i) { //把跟i相连的城市化0
        for (int k = 0; k < m.size(); k++) {
            if (m[i][k] == 1) {
                m[i][k] = 0;
                m[k][i] = 0;
                re(m, k);
            }
        }
    }
    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 (m[i][j] == 1) {
                    count++;
                    re(m, i);
                    continue;
                }
            }
        }
        return count;
    }
};

理解清楚题意很重要。

递归模块主要是，在count++之后将一个城市群的连接全断掉。