How to use Disjoint Set And Adjacency List In Data Structures and Algorithms

Q: How to use Disjoint Set And Adjacency List In Data Structures and Algorithms

Here We use disjoint set to calculate extra connections between computers then using disjoint set method call findupar() then we will calculate the total number of components of graph. Now. we have k i.e extra edges & n i.e number of components in graph. if((totalcomponents-1)<=k)return totalcomponents-1; // totalcomponents-1 must be less then extra edges in all components to connect all to each other. else return -1; // if not return -1.

Minimize count of connections using Minimum Spanning Tree

  Here We use disjoint set to calculate extra connections between computers then using disjoint set method 
  call findupar() then we will calculate the total number of components of graph.
  Now.
    we have k i.e extra edges
    &
    n i.e number of components in graph.
    
    if((totalcomponents-1)<=k)return totalcomponents-1; // totalcomponents-1 must be less then extra edges in all 
                                                         components to connect all to each other.
    else return -1;     // if not return -1.

Follow the steps below to solve the problem:

Make adjacency list from given 2D array.
Call disjoint class with given number of computers.
Calculate total number of components in graph using dfs.
Last step check totalcomponents – 1 <= totalnumberofextraedges.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h>
#include <iostream>
 
using namespace std;
 
class DisjointSet {
    vector<int> rank, parent, size;
 
public:
    DisjointSet(int n)
    {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1);
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
 
    int findUPar(int node)
    {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }
 
    void unionByRank(int u, int v)
    {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v)
            return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
 
    void unionBySize(int u, int v)
    {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v)
            return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
};
 
void dfs(int start, vector<int> adj[], vector<bool>& vis)
{
    if (vis[start])
        return;
    vis[start] = 1;
    for (auto it : adj[start]) {
        dfs(it, adj, vis);
    }
}
 
int main(){
    int n = 6;
    vector<vector<int> > connections{
      {0,1},{0,2},{0,3},{1,2},{1,3}
    };
    vector<int> adj[n + 1];
    for (int i = 0; i < connections.size(); i++) {
        adj[connections[i][0]].push_back(connections[i][1]);
        adj[connections[i][1]].push_back(connections[i][0]);
    }
    DisjointSet ds(n);
    int extra = 0;
    for (int i = 0; i < connections.size(); i++) {
        if (ds.findUPar(connections[i][0])
            == ds.findUPar(connections[i][1]))
            ++extra;
        ds.unionBySize(connections[i][0],
                       connections[i][1]);
    }
    vector<bool> vis(n, 0);
    dfs(0, adj, vis);
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            ++cnt;
            dfs(i, adj, vis);
        }
    }
    if (cnt <= extra) {
        cout << cnt << endl;
    }
    else {
        cout << "All computer can not be connect "
             << endl;
        cout<<-1<<endl;
    }
  //code and approach contributed by Sanket Gode.
    return 0;
}

Java

import java.util.*;
 
class DisjointSet {
    private int[] rank, parent, size;
 
    public DisjointSet(int n)
    {
        rank = new int[n + 1];
        parent = new int[n + 1];
        size = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            size[i] = 1;
        }
    }
 
    public int findUPar(int node)
    {
        if (node == parent[node])
            return node;
        return parent[node] = findUPar(parent[node]);
    }
 
    public void unionByRank(int u, int v)
    {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v)
            return;
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
 
    public void unionBySize(int u, int v)
    {
        int ulp_u = findUPar(u);
        int ulp_v = findUPar(v);
        if (ulp_u == ulp_v)
            return;
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
}
 
public class GFG {
 
    public static void
    dfs(int start, ArrayList<Integer>[] adj, boolean[] vis)
    {
        if (vis[start])
            return;
        vis[start] = true;
        for (int it : adj[start]) {
            dfs(it, adj, vis);
        }
    }
 
    public static void main(String[] args)
    {
        int n = 6;
        ArrayList<int[]> connections
            = new ArrayList<int[]>(Arrays.asList(
                new int[] { 0, 1 }, new int[] { 0, 2 },
                new int[] { 0, 3 }, new int[] { 1, 2 },
                new int[] { 1, 3 }));
        ArrayList<Integer>[] adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < connections.size(); i++) {
            int u = connections.get(i)[0],
                v = connections.get(i)[1];
            adj[u].add(v);
            adj[v].add(u);
        }
        DisjointSet ds = new DisjointSet(n);
        int extra = 0;
        for (int i = 0; i < connections.size(); i++) {
            int u = connections.get(i)[0],
                v = connections.get(i)[1];
            if (ds.findUPar(u) == ds.findUPar(v))
                ++extra;
            ds.unionBySize(u, v);
        }
        boolean[] vis = new boolean[n];
        dfs(0, adj, vis);
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            if (!vis[i]) {
                ++cnt;
                dfs(i, adj, vis);
            }
        }
        if (cnt <= extra) {
            System.out.println(cnt);
        }
        else {
            System.out.println(
                "All computer can not be connect ");
            System.out.println(-1);
        }
      // Code is Contributed by Vikas Bishnoi
    }
}

Python3

from typing import List
 
class DisjointSet:
    def __init__(self, n: int) -> None:
        self.rank = [0] * (n + 1)
        self.parent = list(range(n + 1))
        self.size = [1] * (n + 1)
 
    def findUPar(self, node: int) -> int:
        if node == self.parent[node]:
            return node
        self.parent[node] = self.findUPar(self.parent[node])
        return self.parent[node]
 
    def unionByRank(self, u: int, v: int) -> None:
        ulp_u = self.findUPar(u)
        ulp_v = self.findUPar(v)
        if ulp_u == ulp_v:
            return
        if self.rank[ulp_u] < self.rank[ulp_v]:
            self.parent[ulp_u] = ulp_v
        elif self.rank[ulp_v] < self.rank[ulp_u]:
            self.parent[ulp_v] = ulp_u
        else:
            self.parent[ulp_v] = ulp_u
            self.rank[ulp_u] += 1
 
    def unionBySize(self, u: int, v: int) -> None:
        ulp_u = self.findUPar(u)
        ulp_v = self.findUPar(v)
        if ulp_u == ulp_v:
            return
        if self.size[ulp_u] < self.size[ulp_v]:
            self.parent[ulp_u] = ulp_v
            self.size[ulp_v] += self.size[ulp_u]
        else:
            self.parent[ulp_v] = ulp_u
            self.size[ulp_u] += self.size[ulp_v]
 
def dfs(start: int, adj: List[List[int]], vis: List[bool]) -> None:
    if vis[start]:
        return
    vis[start] = True
    for it in adj[start]:
        dfs(it, adj, vis)
 
if __name__ == '__main__':
    n = 6
    connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
    adj = [[] for _ in range(n + 1)]
    for u, v in connections:
        adj[u].append(v)
        adj[v].append(u)
    ds = DisjointSet(n)
    extra = 0
    for u, v in connections:
        if ds.findUPar(u) == ds.findUPar(v):
            extra += 1
        ds.unionBySize(u, v)
    vis = [False] * n
    dfs(0, adj, vis)
    cnt = 0
    for i in range(n):
        if not vis[i]:
            cnt += 1
            dfs(i, adj, vis)
    if cnt <= extra:
        print(cnt)
    else:
        print("All computer can not be connect")
        print(-1)

C#

// Importing required libraries
using System;
using System.Collections.Generic;
 
// Creating a DisjointSet class
class DisjointSet
{
   
    // Defining class variables
    List<int> rank, parent, size;
   
    // Constructor to initialize the class variables
    public DisjointSet(int n)
    {
        rank = new List<int>();
        parent = new List<int>();
        size = new List<int>();
        for (int i = 0; i <= n; i++) {
            rank.Add(0);
            parent.Add(i);
            size.Add(1);
        }
    }
 
    // Method to find the parent of a node using path
    // compression
    public int FindUPar(int node)
    {
        if (node == parent[node]) {
            return node;
        }
        parent[node] = FindUPar(parent[node]);
        return parent[node];
    }
 
    // Method to perform union by rank
    public void UnionByRank(int u, int v)
    {
        int ulp_u = FindUPar(u);
        int ulp_v = FindUPar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        }
        else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        }
        else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }
 
    // Method to perform union by size
    public void UnionBySize(int u, int v)
    {
        int ulp_u = FindUPar(u);
        int ulp_v = FindUPar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        }
        else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }
}
 
// Main function
class Program {
    static void dfs(int start, List<int>[] adj,
                    ref List<bool> vis)
    {
        if (vis[start]) {
            return;
        }
        vis[start] = true;
        foreach(int it in adj[start])
        {
            dfs(it, adj, ref vis);
        }
    }
    static void Main(string[] args)
    {
        // Initializing the input values
        int n = 6;
        List<List<int> > connections = new List<List<int> >{
            new List<int>{ 0, 1 }, new List<int>{ 0, 2 },
            new List<int>{ 0, 3 }, new List<int>{ 1, 2 },
            new List<int>{ 1, 3 }
        };
        List<int>[] adj = new List<int>[ n + 1 ];
        for (int i = 0; i <= n; i++) {
            adj[i] = new List<int>();
        }
        foreach(List<int> con in connections)
        {
            adj[con[0]].Add(con[1]);
            adj[con[1]].Add(con[0]);
        }
        DisjointSet ds = new DisjointSet(n);
        int extra = 0;
        foreach(List<int> con in connections)
        {
            if (ds.FindUPar(con[0])
                == ds.FindUPar(con[1])) {
                extra++;
            }
            ds.UnionBySize(con[0], con[1]);
        }
        List<bool> visited = new List<bool>();
        for (int i = 0; i <= n; i++) {
            visited.Add(false);
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(i, adj, ref visited);
                count++;
            }
        }
        if (extra >= count - 1) {
            Console.WriteLine(count - 1);
        }
        else {
            Console.WriteLine("Not possible");
        }
    }
}

Javascript

class DisjointSet {
    constructor(n) {
        this.rank = new Array(n + 1).fill(0);
        this.parent = new Array(n + 1);
        this.size = new Array(n + 1);
        for (let i = 0; i <= n; i++) {
            this.parent[i] = i;
            this.size[i] = 1;
        }
    }
 
    findUPar(node) {
        if (node === this.parent[node])
            return node;
        return this.parent[node] = this.findUPar(this.parent[node]);
    }
 
    unionByRank(u, v) {
        const ulp_u = this.findUPar(u);
        const ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v)
            return;
        if (this.rank[ulp_u] < this.rank[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
        } else if (this.rank[ulp_v] < this.rank[ulp_u]) {
            this.parent[ulp_v] = ulp_u;
        } else {
            this.parent[ulp_v] = ulp_u;
            this.rank[ulp_u]++;
        }
    }
 
    unionBySize(u, v) {
        const ulp_u = this.findUPar(u);
        const ulp_v = this.findUPar(v);
        if (ulp_u === ulp_v)
            return;
        if (this.size[ulp_u] < this.size[ulp_v]) {
            this.parent[ulp_u] = ulp_v;
            this.size[ulp_v] += this.size[ulp_u];
        } else {
            this.parent[ulp_v] = ulp_u;
            this.size[ulp_u] += this.size[ulp_v];
        }
    }
}
 
function dfs(start, adj, vis) {
    if (vis[start])
        return;
    vis[start] = true;
    for (const it of adj[start]) {
        dfs(it, adj, vis);
    }
}
 
    const n = 6;
    const connections = [
        [0, 1], [0, 2], [0, 3], [1, 2], [1, 3]
    ];
    const adj = new Array(n + 1).fill(null).map(() => []);
    for (const conn of connections) {
        adj[conn[0]].push(conn[1]);
        adj[conn[1]].push(conn[0]);
    }
    const ds = new DisjointSet(n);
    let extra = 0;
    for (const conn of connections) {
        if (ds.findUPar(conn[0]) === ds.findUPar(conn[1]))
            extra++;
        ds.unionBySize(conn[0], conn[1]);
    }
    const vis = new Array(n).fill(false);
    dfs(0, adj, vis);
    let cnt = 0;
    for (let i = 0; i < n; i++) {
        if (!vis[i]) {
            cnt++;
            dfs(i, adj, vis);
        }
    }
    if (cnt <= extra) {
        console.log(cnt);
    } else {
        console.log("All computers cannot be connected");
        console.log(-1);
    }
    // Code and approach contributed by Sanket Gode.

Output

Time Complexity: O(n) i.e DFS . The disjoint set function work in almost constant time.
Auxiliary Space: O (V + E).

Minimize count of connections required to be rearranged to make all the computers connected

Given an integer N, denoting the number of computers connected by cables forming a network and a 2D array connections[][], with each row (i, j) representing a connection between i^th and j^th computer, the task is to connect all the computers either directly or indirectly by removing any of the given connections and connecting two disconnected computers If it’s not possible to connect all the computers, print -1. Otherwise, print the minimum number of such operations required.

Examples:

Input: N = 4, connections[][] = {{0, 1}, {0, 2}, {1, 2}}
Output: 1
Explanation: Remove the connection between computers 1 and 2 and connect the computers 1 and 3.

Input: N = 5, connections[][] = {{0, 1}, {0, 2}, {3, 4}, {2, 3}}
Output: 0

Tags:

#connected-components #DFS #Minimum Spanning Tree #DSA #Graph #Greedy #Mathematical #Recursion #DFS #Graph #Greedy #Mathematical #Recursion