FastPrep
Problem · Graph

Connected Sum

Learn this problem
● MediumAtlassian logoAtlassianFULLTIMEOA

Problem statement

Given an undirected graph with nodes 1 through n, find every connected-component size. Return the sum of ceil(sqrt(size)) over all components.

Function

connectedSum(n: int, graphFrom: int[], graphTo: int[]) → int

Examples

Example 1

n = 6graphFrom = [1,2,4]graphTo = [2,3,5]return = 5

Component sizes are 3, 2, and 1, contributing 2 + 2 + 1.

Constraints

  • 1 <= n <= 200000
  • Edges join valid distinct node IDs.

More Atlassian problems

drafts saved locally
public int connectedSum(int n, int[] graphFrom, int[] graphTo) {
  // Write your code here.
}
n6
graphFrom[1,2,4]
graphTo[2,3,5]
expected5
checking account