HackerRank Components in a graph problem solution

In this HackerRank Components in a graph problem, we have given a list of edges, and we need to determine the size of the smallest and largest connected components that have 2 or more nodes.

Problem solution in Python programming.

from collections import defaultdict

n = int(input())
A = defaultdict(lambda: [])
for _ in range(n):
    a, b = map(int, input().split())
    A[a].append(b)
    A[b].append(a)

low = high = None

U = set(A)
S = set()
for u in U:
    if u not in S:
        i = 0
        V = [u]
        T = set()
        T.add(u)
        
        while i < len(V):
            v = V[i]
            S.add(v)
            i += 1
            for w in A[v]:
                if w not in T:
                    T.add(w)
                    V.append(w)

        if low is None or i < low:
            if i == 1:
                print("i", i, "S", S, "T", T, "u", u)
            low = i
        if high is None or i > high:
            high = i
print(low, high)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] parent = new int[2 * n + 1];
        int[] count = new int[2 * n + 1];
        for (int i = 1; i <= 2 * n; i++) {
            count[i] = 1;
            parent[i] = i;
        }
        for (int i = 0; i < n; i++) {
            int g = scanner.nextInt();
            int b = scanner.nextInt();           
            int root_g = g;
            int root_b = b;
            while (parent[root_g] != root_g) root_g = parent[root_g];
            while (parent[root_b] != root_b) root_b = parent[root_b];
            if (root_b == root_g) continue;
            if (count[root_b] < count[root_g]) {
                parent[root_b] = root_g;
                count[root_g] += count[root_b];
            } else {
                parent[root_g] = root_b;
                count[root_b] += count[root_g];               
            }
            //System.out.println(g + "::" + b);
            //System.out.println(parent[g] + "->" + parent[b]);
        }
        int min = 2 * n + 1;
        int max = 2;
        for (int i = 1; i <= 2 * n; i++) {
            if (parent[i] != i) continue;
            if (count[i] == 1) continue;
            min = Math.min(min, count[i]);
            max = Math.max(max, count[i]);
            //System.out.println(i + ":" + count[i]);
        }
        System.out.println(min + " " + max);
    }
}

Problem solution in C++ programming.

#include<bits/stdc++.h>
#include<fstream>
using namespace std;
int t, n, m, i, j, parent[30005], sum[30005], ans,ans1;
int a, b;
int find(int x)
{
    if (x == parent[x])
        return parent[x];
    else
        return parent[x]=find(parent[x]);
}
int main()
{
        //ifstream inp;
        //ofstream out;
        ans = 2,ans1=200000000;
        cin>>n;
        assert(n<=15000);
        for (i = 1; i <= 2*n; i ++)
        {
            parent[i] = i;
            sum[i] = 1;
        }
        for (i = 0; i < n; i++)
        {
            cin>>a>>b;
            assert(a<=n&&a>=1);
            assert(b>=(n+1)&&b<=2*n);
            int pa = find(a);
            int pb = find(b);
            if (pa != pb)
            {
                parent[pa] = pb;
                sum[pb] += sum[pa];
            }
        }
        for (i = 1; i <= 2*n; i ++)
        {
            if(sum[i]!=1){
            int ind=find(i);
            ans1=min(sum[ind],ans1);
            }
        }
        for (i = 1; i <= 2*n; i ++)
        {
            if(sum[i]!=1){
            int ind1=find(i);
            ans=max(sum[ind1],ans);
            }
        }
        cout<<ans1<<" "<<ans<<endl;

        //printf("%dn", ans);
    return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

typedef struct Node{
    int cnt;
    int par;
}node;

node *com_array;
int low=0,high=0;

int find_parent(int n){
    while(com_array[n].par != -1){
        n=com_array[n].par;
    }
    return n;
}

void find_low(int n){
    int par;
    for(int i=0;i<2*n;i++){
        par=find_parent(i);
        com_array[i].cnt=com_array[par].cnt;
        if((com_array[i].cnt>1) && (com_array[i].cnt<low)) low=com_array[i].cnt;
    }
}

void mergeCom(int p1, int p2){
    int max,less,par1,par2;
    if(p1==p2) return;
    par1=find_parent(p1);
    par2=find_parent(p2);

    if((par1>=0) &&  ( par1 == par2)) return;
    
    if(com_array[par1].cnt>=com_array[par2].cnt){
        max=par1;
        less=par2;
    }
    else{
        max=par2;
        less=par1;
    }
    com_array[max].cnt+=com_array[less].cnt;
    com_array[less].par=max;
    if(com_array[max].cnt>high) high=com_array[max].cnt;
}



int main() {
    int n;
    int i,p1,p2;
    scanf("%d",&n);
    low=2*n;
    com_array=(node*)malloc(2*n*sizeof(node));
    for(i=0;i<2*n;i++){
        com_array[i].par=-1;
        com_array[i].cnt=1;
    }
    for(i=0;i<n;i++){
         scanf("%d %d",&p1,&p2);   
         mergeCom(p1-1,p2-1);
    }
    find_low(n);
    printf("%d %dn",low,high);
    return 0;
}

Problem solution in JavaScript programming.

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the componentsInGraph function below.
 */
function componentsInGraph(gb) {
    /*
     * Write your code here.
     */
    const n = gb.length;
    // initialize disjoint sets
    const sets = Array(2 * n);
    for (let i=0; i<2*n; i++) {
        sets[i] = {
            count: 1,
            idx: i,
        };
    }
    
    gb.forEach((e) => {
        const s1 = findSet(sets, e[0] - 1);
        const s2 = findSet(sets, e[1] - 1);
        if (s1.idx !== s2.idx) {
            // merge two sets
            mergeSets(s1, s2);
        }
    });
    
    let min = Infinity, max = 0;
    sets.forEach((set, idx) => {
        if (set.idx === idx) {
            if (max < set.count) {
                max = set.count;
            }
            if (set.count > 1 && min > set.count) {
                min = set.count;
            }
        }
    });
    return [min, max];
}

function findSet(sets, d) {
    let s = d;
    while(sets[s].idx !== s) {
        s = sets[s].idx;
    }
    return sets[s];
}

function mergeSets(set1, set2) {
    let small = set1;
    let large = set2;
    if (set1.count > set2.count) {
        small = set2;
        large = set1;
    }
    small.idx = large.idx;
    large.count = small.count + large.count;
    small.count = large.count;
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine(), 10);

    let gb = Array(n);

    for (let gbRowItr = 0; gbRowItr < n; gbRowItr++) {
        gb[gbRowItr] = readLine().split(' ').map(gbTemp => parseInt(gbTemp, 10));
    }

    let result = componentsInGraph(gb);

    ws.write(result.join(" ") + "n");

    ws.end();
}