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("%d\n", 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 %d\n",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();
}
0 Comments