분리된 이중문자 수 세기

Question

나는 boolean[][] 2D 배열 호출 matrix, 이는 다음과 같은 방향성 그래프를 인코딩합니다. matrix[i][j] == true, 정점 제이 정점에 연결되어 있다 나 (반대가 반드시 참인 것은 아닙니다).
나는 얼마나 많은 분리된 방향성 그래프가 있는지 결정하는 Java 메서드를 만들려고 합니다.

그래서 예, 정점 0이 정점 1에 연결되고 정점 2가 정점 3에 연결된 경우(<code>[{{0,0,0,0},{1,0,0,0},{0,0,0,0},{0,0,1,0}}]</code> would be the 2D array), 나는 2개의 분리된 이중문자를 갖게 될 것입니다.

연결이 없는 경우, 분리된 이중 그래프의 수는 정점의 수와 같습니다.

Answer 1

트리의 모든 노드 목록으로 시작합니다.사용하지 않은 노드를 고려하십시오.

는 사용되지 않은 노드 목록이 사라지기를 때까지 다음 과정을 반복합니다.

1. 현재 노드 그래프에 사는 노드를 나타내는 "노드 집합"이 빈 세트를 만듭니다.
2. 현재 노드에서 시작하는 검색을 수행합니다.검색에서 발생한 각 노드에 대해 사용하지 않는 노드 목록에서 제거한 다음 : (1) 노드가 이미 다른 노드 집합에있는 경우 이미 있으면 현재 노드 세트를 병합하고 다른 노드 세트를 병합하고 검색을 중지하십시오.해당 노드가 현재 노드 집합에 이미 존재하는 경우 해당 노드에서 해당 노드에서 검색을 중지하거나 해당 노드를 보지 못한 경우 현재 노드 세트에 추가하십시오.

   이 프로세스가 완료되면 노드 세트가 각 분리 그래프에 고유하게 존재하는 노드와 일치하므로 노드 세트 수는 사용자가 추구하는 값입니다.

Answer 2

강력한 연결이 필요하지 않은 것 같습니다. Disjoint-Set Forest에 대한 매우 효과적인 알고리즘 작업을 수행합니다.노조 단계 후에는 부모= 자체로 노드를 계산해야합니다

p.s. IT에 대한 Sedgewick Lection

Answer 3

public int countDisjointSubgraphs() {
    int len = matrix.length;
    int[] nodes = new int[len];
    for (int i = 0 ; i < len ; i++) nodes[i] = i;
    for (int i = 0 ; i < len ; i++) {
        for (int j = 0 ; j < len ; j++) {
            if (matrix[i][j] || matrix[j][i])
                for (int k = 0 ; k < len ; k++)
                    if (nodes[k] == nodes[i]) nodes[k] = j;
        }
    }
    ArrayList<Integer> list = new ArrayList<Integer>();
    for (int i : nodes)
        if (list.indexOf(i) < 0) list.add(i);
    return list.size();
}

.