We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
func maxCircle(queries: [[Int]]) -> [Int] {
// Create a dictionary to track the parent of each element (set representative)
var parent = [Int: Int]() // Parent dictionary to track set representatives
// Create a dictionary to track the size of each set
var size = [Int: Int]() // Size of each set
// Function to find the set representative (with path compression)
func find(_ x: Int) -> Int {
// If the element is not in the parent dictionary, create a new set with itself
if parent[x] == nil {
parent[x] = x
size[x] = 1
return x
}
// Find the root (set representative) of the element
var root = x
while parent[root] != root {
root = parent[root]!
}
// Path compression: Update the parent of elements on the path to the root
var current = x
while current != root {
let next = parent[current]!
parent[current] = root
current = next
}
return root
}
// Function to union two sets based on their representatives (with union by size)
func union(_ a: Int, _ b: Int) -> Int {
// Find the representatives of the two sets
let rootA = find(a)
let rootB = find(b)
// If the elements are in different sets, merge them based on size
if rootA != rootB {
// Union by size: Attach the smaller set to the larger set
if size[rootA]! < size[rootB]! {
parent[rootA] = rootB
size[rootB]! += size[rootA]!
return size[rootB]!
} else {
parent[rootB] = rootA
size[rootA]! += size[rootB]!
return size[rootA]!
}
}
// Return the size of the set that the elements belong to
return size[rootA]!
}
// Initialize variables for tracking maximum set size and results
var maxSize = 0
var result = [Int]()
// Process each query in the input
for query in queries {
let a = query[0]
let b = query[1]
// Union the two elements into sets and update the maximum set size
maxSize = max(maxSize, union(a, b))
result.append(maxSize)
}
// Return the results containing maximum set sizes after each query
return result
}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Friend Circle Queries
You are viewing a single comment's thread. Return to all comments →
in swift
}