글 읽기 - 유니온 파인드 집합의 갯수 질문드립니다 (파이썬set질문)

kgood1 3년 전 0

ccw알고리즘을 사용하여 경로압축을 써서 풀어봤습니다

총 집합의 갯수를 구하려면 부모노드리스트를 set자료형으로 만들면 될거라고 생각했습니다.

ex) [0,0,0,0,4]이면 {0,4}가 되어 2개의 집합이 있게 된다고 생각했습니다.

하지만 set자료형으로 만든 것은 통과하지못하고

for i in range(n) 문에서 parent[i]==i인것의 갯수를 출력해야 답이였습니다

두개의 차이가 뭔지 알려주실수있을까요?? 맨밑에 5줄만 보셔도됩니다

반례를 들어주셔도 감사하겠습니다

import sys
input=sys.stdin.readline
def find(v):
    if parent[v]==v:
        return v
    else:
        parent[v]=find(parent[v])
        return parent[v]
def merge(a,b):
    q=find(a)
    w=find(b)
    if q==w:
        return
    else:
        if q<w:
            parent[w]=q
            cnt[q]+=cnt[w]
        else:
            parent[q]=w
            cnt[w]+=cnt[q]
def sinbal(a,b,c):
    return (a[0]*b[1]+b[0]*c[1]+c[0]*a[1])-(a[1]*b[0]+b[1]*c[0]+c[1]*a[0])
def ccw(a,b):
    fx=a[0:2]
    fy=a[2:]
    sx=b[0:2]
    sy=b[2:]
    first=sinbal(fx,fy,sx)*sinbal(fx,fy,sy)
    second=sinbal(sx,sy,fx)*sinbal(sx,sy,fy)
    if first==0 and second==0:
        if fx>fy:
            fx,fy=fy,fx
        if sx>sy:
            sx,sy=sy,sx
        if fx<=sy and sx<=fy:
            return True
        else:
            return False
    else:
        if first<=0 and second<=0:
            return True
        else:
            return False

n=int(input())
adj=[]
for i in range(n):
    adj.append(list(map(int,input().split())))
cnt=[1]*n
parent=[i for i in range(n)]
for i in range(n-1):
    for j in range(i+1,n):
        if ccw(adj[i],adj[j]):
            merge(i,j)
ans=0
for i in range(n):
    if parent[i]==i:
        ans+=1
print(ans)    #맞고
#print(len(set(parent))) #틀리고

print(max(cnt))

qera 3년 전 1

경로 압축을 하지 않은 채로 set자료형으로 해서 제대로 안된거 같습니다. 모든 경로에 find함수를 해서 경로 압축을 한다음 set을 사용하시면 제대로 값이 나올거 같습니다.

kgood1 3년 전 1

경로압축이 다 되었다고 생각했네요

감사드려요 ㅎㅎ

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

유니온 파인드 집합의 갯수 질문드립니다 (파이썬set질문)

kgood1 3년 전 0

qera 3년 전 1

kgood1 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말