题目

解题

这道题与海岛不一样，海岛题中的每一个点都是随机的。但是这个是关系图，每一列代表一个节点，而这一列的每一行代表与其他节点的关系。而且相连的几个城市会组成一个省份，没有与其他城市相连的城市自己是一个省份。我们需要知道的是有几个省份，那吗就应该让每一列出现的次数为1，高于这个次数说明该产城市重复出现，也就是与其他城市相连

/**
 * @param {number[][]} isConnected
 * @return {number}
 * 与海岛题不一样，海岛是随机在海里的，
 * 省份中城市是有连在一起的。 
 * 所以每一列代表一个城市同时代表那个城市与之相连
 */
var findCircleNum = function(isConnected) {
    let len = isConnected.length;
    let total = 0;
    // 一个城市就是一列， 防止其重复出现
    let set = new Set();
    for(let r = 0; r < len; r++) {
        if(!set.has(r)) {
            dfs(isConnected, r, set)
            total++;
        }
    }
    return total;
};
    var dfs = (isConnected, r, set) => {
        const len = isConnected.length;
        for(let c = 0; c < len; c++) {
            // 当为1 说明该城市说明有相连， 将其列号保存起来
            if(isConnected[r][c] === 1 && !set.has(c)) {
                set.add(c); // 保存城市的列号
                // 判断该行的其他列
                dfs(isConnected, c, set) 
            }
        }
    }