# Components in a graph

# Components in a graph

m_kaleia + 2 comments The figure is missing in the description! Anyone has a similar problem?

jordanmprince + 0 comments Same!

dgr8akki + 0 comments Found any solution regarding the same?

Tuxdude + 1 comment Loved this problem, it is simple but it makes you learn a new data structure and how to implement it if you're not already familiar with it.

I was able to pass all the test cases in the problem by implementing a DisjointSet Data Structure. I was just wondering how people were keeping track of the different connected components (for finding the ones with smallest and largest sizes). I used a HashSet in addition to the DisjointSet to achieve this, with each union operation removing one item from this set. Although this works, I was wondering if there are any better ways without using an additional Data Structure here ?maximshen + 1 comment I use an int array (int[] parents) to keep tracking each element's root element, if any elements have the same root element, then they belong to the same set. Then you can just find the frequency of each value within that int[] parents.

Any suggestion is welcome for sure !

public static void main(String[] args) {

`int[] parents = new int[30001]; Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int a, b; while(n-->0){ a = sc.nextInt(); b = sc.nextInt(); System.out.println(a + " " + b); if(parents[a] == 0) parents[a] = a; if(parents[b] == 0) parents[b] = a; //Disjoin set idea, keep updating the representative element of each set. if(parents[a] != 0 || parents[b] != 0){ int low = Math.min(parents[a], parents[b]); int high = Math.max(parents[a], parents[b]); for(int i=0; i<parents.length; i++){ if(parents[i] == high) parents[i] = low; } } } //convert int[] to Integer[] in order to use Collections.frequency(Integer[], int) Integer[] newArray = new Integer[parents.length]; int i = 0; for (int value : parents) { newArray[i++] = value; } List<Integer> ints = Arrays.asList(newArray); int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for(int item : newArray) { if(item != 0) { int frequency = Collections.frequency(ints, item); min = Math.min(min, frequency); max = Math.max(max, frequency); } } System.out.println(min + " " + max); }`

rwan7727 + 1 comment C++ solution, passed all tests:

#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int findset(int x, vector <int> &r) { if (r[x]==x) return(x); else return(findset(r[x],r)); } int main() { int n; cin >> n; // init vector <int> root(2*n+1); vector <int> count(2*n+1); for (int i=1;i<=2*n;i++) { root[i]=i; count[i]=1; } for (int i=0;i<n;i++) { int g,b; cin >> g >> b; // find root of g & b int rg=findset(g,root); int rb=findset(b,root); if (rg==rb) continue; // union without ranking root[rb]=rg; count[rg]+=count[rb]; count[rb]=0; } // find min and max int min=2*n+1; int max=0; for (int i=1;i<=2*n;i++) { if (count[i]>1 && count[i]<min) min=count[i]; if (count[i]>max) max=count[i]; } cout << min << " " << max; return 0; }

tpcemail + 0 comments thanks to share your solution

btamada + 3 comments "The number of vertices in the largest connected component in the graph is 4 i.e. 1−2−6−7."

Shouldn't this actually be 1-6-2-7 since 2 and 6 being connected is what connects the 1-6 and 2-7 pairs?

kiner_shah + 0 comments Same doubt here

radekr_ + 0 comments It doesn't matter really as you look only on size of the group and not individual connections within it. I guess author has chosen to print them in ascending order and "-" signs represents the same as " " sign, not the connections.

realmadrid7pulk1 + 1 comment actually they are just telling that these vertices are involved and not the order

mhelvens + 0 comments Yeah, but I agree that

`1-2-6-7`

is an awkward notation for that. Why not just`{1, 2, 6, 7}`

?

harshdeep27 + 0 comments Take care of repeated edges.

dHyun + 2 comments Very simple Java 8 solution:

import java.io.*; import java.util.*; public class Solution { static class Graph { HashMap<Integer, ArrayList<Integer>> nodes; Graph (int n) { nodes = new HashMap<>(); for (int i = 1; i <= 2*n; i++) { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(i); nodes.put(i, list); } } void set_edge(int n1, int n2) { ArrayList<Integer> list1 = nodes.get(n1); ArrayList<Integer> list2 = nodes.get(n2); if (list1 != list2) { list1.addAll(list2); list2.forEach(i -> nodes.put(i, list1)); } } void print_answer() { ArrayList<Integer> vertices = new ArrayList<Integer>(); for (ArrayList<Integer> list : nodes.values()) { if (list.size() > 1) vertices.add(list.size()); list.clear(); } System.out.print(Collections.min(vertices) + " "); System.out.println(Collections.max(vertices)); } } public static void main(String[] args) { Scanner in = new Scanner(System.in); int N = in.nextInt(); Graph G = new Graph(N); for (int i = 0; i < N; i++) { int n1 = in.nextInt(); int n2 = in.nextInt(); G.set_edge(n1, n2); } G.print_answer(); } }

ashjostan7 + 1 comment Can you please explain how the set_edge function works, havnt understood how the nodes.get() and foreach loop function.

kimdo4354 + 0 comments HashMap value contains a list of vertices in a sub graph where its key belongs. Set edge function merges the two sub graph of given vertices:

- list2 is added to list1
- update vertices in list2 to the new sub graph
- list1 is called by reference, so it doesn't need to be updated

realmadrid7pulk1 + 0 comments import java.io.

*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*;public class Solution { public static int dfs (int arr[][],boolean visited[],int k) { visited[k]=true; int count =1; for(int i=1;i }

} return count; } 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 in = new Scanner(System.in); int n = in.nextInt(); int arr[][]= new int [2*n+1][2*n+1]; for(int i =0;i } int min = Integer.MAX_VALUE; int max = Integer.MIN_VALUE; for(int i =1;i<=2*n;i++) { if(visited[i]==false) { int value= dfs(arr,visited,i); if(value==1) continue; if(valuemax) max = value;`} } System.out.println(min+" "+max); }`

} //can u tell why only few test case are passing this code please

iweizmeisk + 1 comment Indeed very weak test cases..passed O(n^2) solution :(

syockit + 0 comments Indeed :p My solution uses a plain random-access array of set IDs. While inserting new set is O(1), merging is O(n), so worst case nears O(n^2) I think.

jaisa_shiv + 1 comment Few test cases are failing for my solution. When I ran the same code externally with concerned test case, the output was same as expected.

Few more people are having the same issue as can be seem in dicussion. Can anyone tell what's the problem ?

saul_mtz_v + 0 comments I had the same problem, use the custom input options, for some weird reason the output showed in the editor was different that the one I got in my IDE

neo_k + 0 comments My BFS based solution:

static class GraphNode { int x; List<GraphNode> neighbors; boolean visited; public GraphNode(int x) { this.x = x; this.neighbors = new ArrayList<>(); } } static int[] componentsInGraph(int[][] gb) { Map<Integer, GraphNode> nodes = buildGraph(gb); int min = Integer.MAX_VALUE; int max = 0; for(GraphNode g : nodes.values()) { int curCount = 0; Queue<GraphNode> q = new LinkedList<>(); q.add(g); while(!q.isEmpty()) { GraphNode poppedNode = q.remove(); if(poppedNode.visited) { continue; } ++curCount; poppedNode.visited = true; for(GraphNode neighbor : poppedNode.neighbors) { q.add(neighbor); } } if(curCount > max) { max = curCount; } if(curCount < min && curCount > 1) { min = curCount; } } return new int[]{min, max}; } private static Map<Integer, GraphNode> buildGraph(int[][] gb) { Map<Integer, GraphNode> sg = new HashMap<>(); for(int i = 0; i < gb.length; ++i) { int n1 = gb[i][0]; int n2 = gb[i][1]; GraphNode gn1 = sg.computeIfAbsent(n1, (v) -> new GraphNode(n1)); GraphNode gn2 = sg.computeIfAbsent(n2, (v) -> new GraphNode(n2)); gn1.neighbors.add(gn2); gn2.neighbors.add(gn1); } return sg; }

danielmanor2018 + 0 comments I'd delegate this problem to service where I do my trigonometry homework.

forteddyt + 0 comments Here's a Java 8 solution.

The general idea for my solution is to convert the

`gb`

input they gave into a (psuedo) AdjacencyList, then DFS through every vertex I have not visited. As I DFS, I keep track of a counter that counts how many vertices I visit during that traversal. Once I finish the DFS, I update my`smallest`

and`largest`

variables, reset counter, DFS the next unvisited vertex, and repeat the process.Once I've visited every vertex, I know I've fully traveresed the graph (and all potential sub-graphs) so I return the

`smallest`

and`largest`

as an`int[]`

.private static HashMap<Integer, ArrayList<Integer>> graph; // class-scoped graph variable private static int curCount; // class scoped vertex counter for current DFS traversal static int[] componentsInGraph(int[][] gb) { graph = buildGraph(gb); // Build the graph HashMap<Integer, Boolean> visited = new HashMap<Integer, Boolean>(); // Similar reasoning for a HashMap here follows reasoning for buildGraph method int shortest = Integer.MAX_VALUE; int longest = 0; // Note that our graph may be a disconnected graph // Consider vertices [1, 4], [1, 5], [3, 6], [3, 7], [3, 8] for(Integer i : graph.keySet()){ // Go through every vertex in the graph if(visited.get(i) == null){ // If that vertex has not yet been visited curCount = 0; // Reset traversal counter to 0 DFSSearch(i, visited); // Traverse it // After traversal, curCount contains the number of vertices in that graph. This may or may not be the only graph longest = Math.max(curCount, longest); shortest = Math.min(curCount, shortest); } } int[] ans = {shortest, longest}; return ans; } // Standard DFS traversal, except on each recursive call, curCount is incremented private static void DFSSearch(int curVal, HashMap<Integer, Boolean> visited){ visited.put(curVal, true); curCount++; // Each recursive call means we go one vertex deeper into the graph for(Integer i : graph.get(curVal)){ // Go through all vertices associated to that vertex if(visited.get(i) == null) { // If that vertex has not yet been visited DFSSearch(i, visited); // Recursively burrow down to that vertex } } } // Converts given 2D array into a graph // Instead of typical adecency list (aka a list of lists), I have a mapping of Vertex to all of its connected Vertices // Since we aren't guarenteed that all edge values will be continious // (ie. we can't guarentee we'll get [1, 4], [2, 5], [3, 6] -- instead we may get [2, 4], [2, 5], [2, 6], notice that 1 and 3 are not present) private static HashMap<Integer, ArrayList<Integer>> buildGraph(int[][] gb){ HashMap<Integer, ArrayList<Integer>> graph = new HashMap<Integer, ArrayList<Integer>>(); for(int[] edge : gb){ int e0 = edge[0]; int e1 = edge[1]; if(graph.get(e0) == null){ graph.put(e0, new ArrayList<Integer>()); } if(graph.get(e1) == null){ graph.put(e1, new ArrayList<Integer>()); } graph.get(e0).add(e1); graph.get(e1).add(e0); } return graph; }

Sort 65 Discussions, By:

Please Login in order to post a comment