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 :



title-img


                            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 →