글 읽기 - 정답 스포 주의( 비교

johyesong8686 3년 전 0

두 코드를 비교하는데서 1은 틀리고 2는 맞았습니다.

if(parent[true_p[i]]==parent[y])): #부모가 같은 지 비교

이 부분 이 다른데 parent 만 확인해도 된다고 생각했는데

꼭 find로 비교해야하는 이유가 있나요 ?

#####1

import sys
n,m =map(int,input().split())
ans=m
true_p=list(map(int,input().split()))[1:]
partyArr=[]
parent=[0]*(n+5)

def find(x):
  if(parent[x]==x): 
    return x
  else :
    x = find(parent[x])
    return x

def union(x,y):
  x=find(x)
  y=find(y)
  if(x<y):
    parent[y]=x
  else :
    parent[x]=y

for _ in range(m):
  party=list(map(int,sys.stdin.readline().rsplit()))[1:]
  partyArr.append(party)

for i in range(n):
  parent[i+1]=i+1


for i in range(len(partyArr)): #같은 파티 끼리 union-find
  for j in range(len(partyArr[i])-1):
    x=partyArr[i][j]
    y=partyArr[i][j+1]
    union(x,y)


cnt=0
for x in partyArr:
  check=False
  for y in x:
    if(check):
      break
    for i in range(len(true_p)):
      if(parent[true_p[i]]==parent[y])): #부모가 같은 지 비교
        check=True
        break
  if check:
    cnt+=1

print(m-cnt)
      
    


####2
import sys
n,m =map(int,input().split())
ans=m
true_p=list(map(int,input().split()))[1:]
partyArr=[]
parent=[0]*(n+5)

def find(x):
  if(parent[x]==x): 
    return x
  else :
    x = find(parent[x])
    return x

def union(x,y):
  x=find(x)
  y=find(y)
  if(x<y):
    parent[y]=x
  else :
    parent[x]=y

for _ in range(m):
  party=list(map(int,sys.stdin.readline().rsplit()))[1:]
  partyArr.append(party)

for i in range(n):
  parent[i+1]=i+1


for i in range(len(partyArr)): #같은 파티 끼리 union-find
  for j in range(len(partyArr[i])-1):
    x=partyArr[i][j]
    y=partyArr[i][j+1]
    union(x,y)


cnt=0
for x in partyArr:
  check=False
  for y in x:
    if(check):
      break
    for i in range(len(true_p)):
      if(find(true_p[i])==find(y)): #부모가 같은 지 비교
        check=True
        break
  if check:
    cnt+=1

print(m-cnt)
      
    
     

Green55 3년 전 1

4=>1<=2<=3

이 경우 3과 4의 부모는 다르지만, 루트는 같습니다. find()가 루트를 찾아주는 역할이고, 항상 루트로 비교해야 합니다.

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

문제

문제

출처

ICPC

정답 스포 주의( 비교

johyesong8686 3년 전 0

Green55 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말