## Algorithm

Problem Name: Data Structures - Components in a graph

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]]

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

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 &

### #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 &

### #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 &

### #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();
});

return inputString[currentLine++];
}

/*
* Complete the componentsInGraph function below.
*/
function componentsInGraph(gb) {
/*
*/
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);

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 &

### #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()

while i < len(V):
v = V[i]
i += 1
for w in A[v]:
if w not in T:
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 &