Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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;
}
#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);
}
}
#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();
}
#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)