Algorithm


Problem Name: Data Structures - Components in a graph

Problem Link: https://www.hackerrank.com/challenges/components-in-graph/problem?isFullScreen=true

In this HackerRank in Data Structures - Components in a graph solutions

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N inclusive. The second node will be between N + 1 and 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have 2 or more nodes. A node can have any number of connections. The highest node value will always be connected to at least 1 other node.

Note Single nodes should not be considered in the answer.

Example

bg = [[1,5],[2,4][2,6]]

image
The smaller component contains 2 nodes and the larger contains 3 Return the array [2,3].

Function Description
Complete the connectedComponents function in the editor below.

 

connectedComponents has the following parameter(s):
- int bg[n][2]: a 2-d array of integers that represent node ends of graph edges

 

Returns
- int[2]: an array with 2 integers, the smallest and largest component sizes

Input Format

The first line contains an integer n, the size of bg.

Each of the next n lines contain two space-separated integers, bg[i][0] and bg[i][1].

Constraints

  • 1<= numberofnodesN <= N 15000
  • 1 <= bg[i][0] <= N
  • N + 1 bg[i][1] <= 2N

Sample Input

STDIN   Function
-----   --------
5       bg[] size n = 5
1 6     bg = [[1, 6],[2, 7], [3, 8], [4,9], [2, 6]]
2 7
3 8
4 9
2 6

Sample Output

2 4

Explanation

image

Since the component with node 5

contains only one node, it is not considered.

 

The number of vertices in the smallest connected component in the graph is

based on either (3,8) or (4,9) .

The number of vertices in the largest connected component in the graph is 4 i.e.

1 - 2 - 6 - 7.

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - 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 %d\n",low,high>;
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - 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("%d\n", ans>;
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - 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);
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - 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();
}
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming



Homedata structureHackerRank Components in a graph problem solution
HackerRank Components in a graph problem solution
YASH PAL May 13, 2021

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.
HackerRank Components in a graph problem solution


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)
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Queue using Two Stacks solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Balanced Brackets solution in Hackerrank - Hacerrank solution C, C++, java,js, Python