Largest Component Size by Common Factor in Java
In this tutorial, we delve into the concept of the largest component aize by common factor in Java. Given an array of positive integers representing the vertices of a graph where two vertices have an edge if their common factor is greater than 1, the function is to find and return the size of the largest connected component of the graph.
Example:
Input: nums = [8, 12, 15]
Output: Largest Component Size: 3
Explanation:
Node 1 (8): GCD(8, 12) = 4, it is connected to node 2 (12).
Node 2 (12): GCD(12, 15) = 3, it is connected to node 3 (15).
Node 3 (15): Has no connections to other nodes and no shared characteristics with them.
The three nodes {8, 12, 15} create a connected component.
Union Find Approach
The provided Java code defines the LargestComponentSize class, which uses a union-find approach to determine the size of the largest connected component in a given array of integers. The withUnionFind() method creates an array called parent, with each element initially set as its parent. It then iterates through the input array's pairs of numbers, checking for common factors with the hasCommonFactor() method. If similar factors are discovered, the union() method is used to combine the components of the corresponding integers. To efficiently discover a component's root, the code uses path compression in the find() method. Finally, the findLargestComponentSize() method computes the sizes of all connected components and returns the largest one.
FileName: LargestComponentSize.java
import java.util.*;
public class LargestComponentSize {
// Method to solve the problem using brute force
public static void withUnionFind (int[] nums) {
int n = nums.length;
int[] parent = new int[n];
// Initialize each element as its own parent
for (int i = 0; i < n; i++) {
parent[i] = i;
}
// Iterate through each pair of numbers to find common factors and union their components
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hasCommonFactor(nums[i], nums[j])) {
union(parent, i, j);
}
}
}
// Calculate the size of the largest connected component
int maxSize = findLargestComponentSize(parent);
System.out.println("Largest Component Size: " + maxSize);
}
// Method to check if two numbers have a common factor
private static boolean hasCommonFactor(int a, int b) {
// Implement GCD calculation
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a > 1; // GCD is greater than 1 if there's a common factor
}
// Method to perform union of two components
private static void union(int[] parent, int a, int b) {
int rootA = find(parent, a);
int rootB = find(parent, b);
// If roots are different, set the root of B as a child of A
if (rootA != rootB) {
parent[rootB] = rootA;
}
}
// Method to find the root of a component using path compression
private static int find(int[] parent, int node) {
if (parent[node] == node) {
return node;
}
return find(parent, parent[node]);
}
// Method to find the size of the largest connected component
private static int findLargestComponentSize(int[] parent) {
Map<Integer, Integer> componentSizes = new HashMap<>();
for (int i = 0; i < parent.length; i++) {
int root = find(parent, i);
componentSizes.put(root, componentSizes.getOrDefault(root, 0) + 1);
}
// Find and return the maximum size among all components
int maxSize = Collections.max(componentSizes.values());
return maxSize;
}
// Main method to test the functionality
public static void main(String[] args) {
int[] nums = {8, 12, 15};
withUnionFind(nums);
}
}
Output:
Largest Component Size: 3
Complexity Analysis: The code's time complexity is O(n^2), where n represents the length of the input array and space complexity is O(n).
Graph Traversal Approach
The provided Java code, encapsulated in the class LargestComponentSize1, uses a graph traversal technique to calculate the size of the largest connected component within an array of integers. The withGraphTraversal() method creates a graph based on common characteristics between elements and uses Depth-First Search (DFS) to explore and locate linked components. The buildGraph() method creates an undirected graph from adjacency lists, linking nodes that have common factors. The dfs() method traverses the graph recursively, marking visited nodes and determining the size of each connected component.
FileName: LargestComponentSize1.java
import java.util.*;
public class LargestComponentSize1 {
public static void withGraphTraversal(int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> graph = buildGraph(nums);
Set<Integer> visited = new HashSet<>();
int maxSize = 0;
for (int i = 0; i < n; i++) {
if (!visited.contains(i)) {
int size = dfs(graph, i, visited);
maxSize = Math.max(maxSize, size);
}
}
System.out.println("Largest Component Size: " + maxSize);
}
// Builds an undirected graph based on common factors between elements.
private static Map<Integer, List<Integer>> buildGraph(int[] nums) {
int n = nums.length;
Map<Integer, List<Integer>> graph = new HashMap<>();
// Initialize the graph with empty adjacency lists
for (int i = 0; i < n; i++) {
graph.put(i, new ArrayList<>());
}
// Connect nodes with common factors
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (hasCommonFactor(nums[i], nums[j])) {
graph.get(i).add(j);
graph.get(j).add(i);
}
}
}
return graph;
}
// Checks if two integers have a common factor.
private static boolean hasCommonFactor(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a > 1;
}
private static int dfs(Map<Integer, List<Integer>> graph, int node, Set<Integer> visited) {
if (visited.contains(node)) {
return 0;
}
visited.add(node);
int size = 1;
for (int neighbor : graph.get(node)) {
size += dfs(graph, neighbor, visited);
}
return size;
}
public static void main(String[] args) {
int[] nums = {8,12,15};
withGraphTraversal(nums);
}
}
Output:
Largest Component Size: 3
Complexity Analysis: The code's time complexity is O(n^2), where n represents the length of the input array and space complexity is O(n^2).