不相交集是kruskal最小生成树中使用的一种数据结构。
这种数据结构允许我们创建两个或多个节点的并集。
它让我们确定两个节点是否属于 not 图的同一组成部分。
时间复杂度为 o(4alpha)（如果我们使用路径压缩，否则它将是对数），这是已被证明的恒定时间复杂度。

更多信息请参考

class Main{
int parent[] = new int[100000];
int rank[] = new int[100000];
void makeSet(){
for(int i=1;i6->4->3 , here 3 is the parent of this union, so in order to get the parent of 7 which is 3 we can path compress it. like 7->3,6->3,4->3 etc.
}
void union(int u, int v){
u = findParent(u);
v = findParent(v);
if(rank[u] rank[v]) parent[v] = u;
else parent[u] =v; // or parent[v] = u;
// here u and v had the same rank
//and now v became parent of u hence its rank will increase
rank[v]++;
}

public static void main(String args[]) throws Exception{
    Main m = new Main();
    //if we where given no of nodes as n
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int n = Integer.parseInt(br.readLine());
    while(n>0){
        int u = n--;
        int v = n--;
        m.union(u,v);// this will create union of n nodes
    }
    // if 2 and 3 belong to the same component or not find out
    if(findParent(2)! = findParent(3)) System.out.println("Different component");
    else System.out.println("Same component");
}

}
登录后复制

    以上就是不相交集图学习的详细内容，更多请关注php中文网其它相关文章！