Components in a graph
Problem Statement :
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 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. 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 ]
Solution :
Solution in C :
In C ++ :
#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;
}
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Element{
int elementId;
int setId;
}
class Set{
int setId;
HashSet<Integer> sets;
}
public class Solution {
Element [] elements;
Set []sets;
void input(){
Scanner sin = new Scanner(System.in);
int N = sin.nextInt();
elements = new Element[2*N];
sets = new Set[2*N];
for(int i = 1; i <= 2*N; i++){
Element e = new Element();
e.elementId = i;
e.setId = i;
elements[i-1] = e;
Set s = new Set();
s.setId = i;
s.sets = new HashSet<Integer>();
s.sets.add(i);
sets[i-1] = s;
}
for(int i = 0; i < N; i++){
int g1 = sin.nextInt();
int b1 = sin.nextInt();
union(g1,b1);
}
int min = 15001;
int max = 0;
for(int i = 0; i < 2*N; i++){
//System.out.println(sets[i].sets.size());
if(sets[i].sets.size() > 1 && sets[i].sets.size() < min){
min = sets[i].sets.size();
}
if(sets[i].sets.size() > max){
max = sets[i].sets.size();
}
}
System.out.println(min+" "+max);
}
void union(int g1, int b1){
if(find(g1,b1)){
}
else{
int set1 = elements[g1-1].setId;
int set2 = elements[b1-1].setId;
Set s1 = sets[set1-1];
Set s2 = sets[set2-1];
if(s1.sets.size() > s2.sets.size()){
Iterator<Integer> iterator = s2.sets.iterator();
while (iterator.hasNext()){
Integer e = iterator.next();
s1.sets.add(e);
elements[e-1].setId = set1;
}
s2.sets.clear();
}
else{
Iterator<Integer> iterator = s1.sets.iterator();
while (iterator.hasNext()){
Integer e = iterator.next();
s2.sets.add(e);
elements[e-1].setId = set2;
}
s1.sets.clear();
}
}
}
boolean find(int g1,int b1){
if(elements[g1-1].setId == elements[b1-1].setId){
return true;
}
else{
return false;
}
}
public static void main(String[] args) {
Solution s = new Solution();
s.input();
}
}
In C :
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h>
//int16_t arr[30010][15010];
int16_t **arr;
int n;
int8_t tmp[30010];
int16_t cnt[30010];
int16_t inp[30010][2];
int d, min, max;
void scan(int k)
{
int i;
for (i = 1; i <= arr[k][0]; i++) {
if (tmp[arr[k][i]] == 0) {
tmp[arr[k][i]] = 1;
d++;
scan(arr[k][i]);
}
}
}
int main() {
int i, j, a, b;
scanf("%d", &n);
arr = (int16_t **) calloc(1, (2 * n + 1) * sizeof(int16_t *));
if (arr == NULL)
return -1;
for(i = 0; i < n; i++) {
scanf("%d%d", &inp[i][0], &inp[i][1]);
cnt[inp[i][0]]++;
cnt[inp[i][1]]++;
}
for(i = 1; i <= 2*n; i++) {
arr[i] = (int16_t *) calloc(1, (cnt[i]+1)*sizeof(int16_t));
if (arr[i] == NULL)
return -1;
}
/*
for(i = 1; i <= 2*n; i++) {
for(j = 0; j <= n; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
*/
// return 0;
for(i = 0; i < n; i++) {
//scanf("%d%d", &a, &b);
a=inp[i][0];
b=inp[i][1];
if (arr[a] == NULL) {
arr[a] = (int16_t *) calloc(1, (n+1)*sizeof(int16_t));
if (arr[a] == NULL)
return -1;
}
if (arr[b] == NULL) {
arr[b] = (int16_t *) calloc(1, (n+1)*sizeof(int16_t));
if (arr[b] == NULL)
return -1;
}
arr[a][0]++;
arr[a][arr[a][0]] = b;
arr[b][0]++;
arr[b][arr[b][0]] = a;
}
//return 0;
/*
for(i = 1; i <= 2*n; i++) {
for(j = 0; j <= n; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
return 0;
*/
/*
for(i = 1; i <= n; i++) {
if (arr[i] == NULL)
continue;
printf("%d -> ", i);
for (j = 1; j <= arr[i][0]; j++) {
printf("%d ", arr[i][j]);
}
printf("\n");
}
*/
min = 2000000000;
max = -1;
for(i = 1; i <= n; i++) {
d = 0;
if (tmp[i] == 0) {
// printf("%d -> ", i);
if (arr[i])
scan(i);
// printf("%d\n", d);
}
if (d < min && d != 0)
min = d;
if (d > max)
max = d;
}
printf("%d %d\n", min, max);
return 0;
}
In Python3 :
from collections import deque, defaultdict
def bfs(g, s):
visited = set()
q = deque([s])
while q:
v = q.popleft()
visited.add(v)
for adj in g[v]:
if adj not in visited and adj not in q:
q.append(adj)
return visited
def con_components(g):
visited = set()
components = []
for s in g.keys():
if s not in visited:
nodes = bfs(g, s)
visited |= nodes
components.append(nodes)
return components
if __name__ == '__main__':
n = int(input())
g = defaultdict(list)
for _ in range(n):
a,b = map(int, input().split())
g[a].append(b)
g[b].append(a)
c = con_components(g)
lens = list(map(len, c))
print(min(lens), max(lens))
View More Similar Problems
Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →Ticket to Ride
Simon received the board game Ticket to Ride as a birthday present. After playing it with his friends, he decides to come up with a strategy for the game. There are n cities on the map and n - 1 road plans. Each road plan consists of the following: Two cities which can be directly connected by a road. The length of the proposed road. The entire road plan is designed in such a way that if o
View Solution →Heavy Light White Falcon
Our lazy white falcon finally decided to learn heavy-light decomposition. Her teacher gave an assignment for her to practice this new technique. Please help her by solving this problem. You are given a tree with N nodes and each node's value is initially 0. The problem asks you to operate the following two types of queries: "1 u x" assign x to the value of the node . "2 u v" print the maxim
View Solution →Number Game on a Tree
Andy and Lily love playing games with numbers and trees. Today they have a tree consisting of n nodes and n -1 edges. Each edge i has an integer weight, wi. Before the game starts, Andy chooses an unordered pair of distinct nodes, ( u , v ), and uses all the edge weights present on the unique path from node u to node v to construct a list of numbers. For example, in the diagram below, Andy
View Solution →Heavy Light 2 White Falcon
White Falcon was amazed by what she can do with heavy-light decomposition on trees. As a resut, she wants to improve her expertise on heavy-light decomposition. Her teacher gave her an another assignment which requires path updates. As always, White Falcon needs your help with the assignment. You are given a tree with N nodes and each node's value Vi is initially 0. Let's denote the path fr
View Solution →