547. 朋友圈

int m;

// LeetCode指定调用方法 
public int findCircleNum(int[][] M) {

    // 记录结果
    int result = 0;

    m = M.length;

    // 标记图中的节点是否被访问
    int[] visited = new int[m];

    for (int i = 0; i < m; i++) {

        // 如果节点i未被搜索则可以进行DFS搜索
        if (visited[i] == 0) {

            // DFS搜索
            dfs(M, visited, i);

            // 更新结果
            result++;
        }
    }

    return result;
}

// DFS
private void dfs(int[][] M, int[] visited, int i) {

    for (int j = 0; j < m; j++) {

        // 如果节点i与节点j相连且节点j没有被访问过则可继续搜索
        if (M[i][j] == 1 && visited[j] == 0) {

            // 被搜索过的节点赋值为1
            visited[j] = 1;

            // 继续搜索
            dfs(M, visited, j);
        }
    }
}

// LeetCode指定调用方法 
public int findCircleNum(int[][] M) {
		
    // 记录结果
    int result = 0;

    int m = M.length;

    // 记录父节点（parent[i] = 0，表示元素i的父元素为0）
    int[] parent = new int[m];

    // 初始化，将每个学生看作一个单元素集合，父节点值赋值为-1（表示当前元素即为根节点）
    for (int i = 0; i < m; i++) {
        parent[i] = -1;
    }

    // 合并M中所有有关系的元素集合
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < i; j++) {
            if (M[i][j] == 1) {
                union(parent, i, j);
            }
        }
    }

    // 统计并查集中合并所有有关系的元素后的集合的数量（数量即为结果）
    for (int i = 0; i < m; i++) {
        if (parent[i] == -1) {
            result++;
        }
    }

    return result;
}

// 查找
private int find(int[] parent, int x){
    if (parent[x] == -1) {
        return x;
    }
    return find(parent, parent[x]);
}

// 合并
private void union(int[] parent, int a, int b){
    int rootA = find(parent, a);
    int rootB = find(parent, b);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}