[백준] 10216번: Count Circle Groups

https://www.acmicpc.net/problem/10216

initial

I tried sorting the circles based on the x and y coordinates and compare each circle via a double for loop. But i wasnt sure how to determine if they are overlapping with each other. BTW the question says even if it overlaps at 1 point, it is considered overlap.

To determine if 2 circles are overlapping use euclidean distance formula. If the euclidean distance is shorter ore equal to the sum of the 2 radius, then they are overlapping.

But i need to see if this logic would work. If they overlap, we minus 1 from our answer, which would be initialised as n cuz they are considered 1 same circle now. I think this logic would work with the double for loop

But anyway the model answer used either dfs or union find. If they overlap, we union them together and we check for each combination via a double for loop. Then we iterate through each node and if we have not seen that node’s parent in our set(), that means it is a new disjoint set so we increment answer.

solution

import math,sys
input = sys.stdin.readline

def find_parent(node, parent):
    if parent[node] != node:
        parent[node] = find_parent(parent[node], parent)
    return parent[node]

def union(node1, node2, parent):
    par1 = find_parent(node1, parent)
    par2 = find_parent(node2, parent)
    if par1 < par2:
        parent[par2] = par1
    else:
        parent[par1] = par2

t = int(input())
for _ in range(t):
    n = int(input())
    lst = []
    parent = [i for i in range(n)]
    
    for _ in range(n):
        a, b, c = map(int, input().split())
        lst.append([a, b, c])

    for i in range(n - 1):
        for j in range(i, n):
            x1, y1, r1 = lst[i]
            x2, y2, r2 = lst[j]
            if math.sqrt((x1 - x2)**2 + (y1 - y2)**2) <= r1 + r2:
                union(i, j, parent)

    check = set()
    ans = 0
    for i in range(n):
        par = find_parent(i, parent)
        if par not in check:
            ans += 1
            check.add(par)

    print(ans)

complexity

union find has ackermann function time complexity
but since it is double for loop is it still n^2?

apparently it is n^2 log n cuz union find here is log n

Let's analyze the time and space complexity of your code:

Time Complexity:

1. Finding Parent in find_parent function:

   • In the worst case, it can take (O(\log n)) time due to path compression.

2. Union Operation in union function:

   • In the worst case, it can take (O(\log n)) time due to the depth of the tree.

3. Loop Iteration for Circle Intersection:

   • There are two nested loops iterating over all pairs of circles, resulting in (O(n^2)) iterations.

4. Total Time Complexity:

   • The overall time complexity is dominated by the nested loops and the union-find operations within them, resulting in (O(n^2 \log n)) in the worst case.

Space Complexity:

1. Parent Array:

   • The parent array has a space complexity of (O(n)) since it stores the representative parent of each node.

2. Additional Data Structures (lst, check, ans):

   • The lst list, check set, and ans variable contribute to constant space, resulting in (O(1)) space complexity.

3. Total Space Complexity:

   • The overall space complexity is (O(n)) due to the parent array.

In summary, the time complexity is (O(n^2 \log n)), and the space complexity is (O(n)). The dominant factor is the union-find operations within the nested loops iterating over all pairs of circles.