Components in a graph| Disjoint Set
Task(medium)
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 2 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.
Example
bg=[[1,5],[1,6],[2,4]]
The smaller component contains 2 nodes and the larger contains 3. Return the array [2,3].
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].
Constraints
1<=numberofnodesN<=15000
1<=bg[i][0]<=N
N+1<=bg[i][1]<=2N
Sample Input
STDIN Function
----- --------
5 bg[] size n = 5
1 6 bg = [[1, 6],[2, 7], [3, 8], [4,9], [2, 6]]
2 7
3 8
4 9
2 6
Sample Output
2 4
SOLUTION 1
def componentsInGraph(gb):
clusters = []
for a, b in gb:
clusters_to_fuse = []
for cluster in clusters:
if a in cluster or b in cluster:
clusters_to_fuse.append(cluster)
if clusters_to_fuse:
fused_cluster = {a, b}
for cluster in clusters_to_fuse:
for node in cluster:
fused_cluster.add(node)
clusters.remove(cluster)
clusters.append(fused_cluster)
else:
clusters.append({a, b})
clusters_len = list(map(len, clusters))
return [min(clusters_len), max(clusters_len)]
SOLUTION 2
def componentsInGraph(gb):
clusters = []
for edge in gb:
clusters_to_fuse = []
for cluster in clusters:
if edge[0] in cluster or edge[1] in cluster:
clusters_to_fuse.append(cluster)
if clusters_to_fuse:
fused_cluster = set(edge)
for cluster in clusters_to_fuse:
for node in cluster:
fused_cluster.add(node)
clusters.remove(cluster)
clusters.append(fused_cluster)
else:
clusters.append(set(edge))
clusters_len = list(map(len, clusters))
return [min(clusters_len), max(clusters_len)]
EXPLANATION STEPS
1.Graph Representation: Choose adjacency list or matrix.
2.Initialization: Create a visited array and construct the graph.
3.Traversal Function: Implement DFS or BFS for exploring nodes.
4.Count Components: Loop through all nodes, apply DFS/BFS for unvisited nodes, and count components.
5.Print Result: Output the number of connected components.
