글 읽기 - [파이썬] 어디가 틀렸을가욥? 조언을 부탁드립니다~!

gyjinro 3년 전 0

아이디어는 아래와 같습니다.

정점 저장 1차 행렬 ver[1001], 정점 부모 1차 행렬 v_p[1001]을 생성

간선을 읽어 오면서 처음 추가되는 정점에 대해 ver, v_p 초기화 및 정점 수(v_cnt) 확인

간선 정보를 활용한 union( v_p값이 낮은 쪽으로) 실행

v_p 값이 최종 부모값을 가질 수 있도록 순환하며 변경

미등장 정점 수 확인 (n - v_cnt)

set(v_p)을 통한 고유값 확보 -1 ('0' 빼기)에 미등장 정점 수 더하기

요렇게 풀었습니다.

다행히(?) 100%까지는 올라갔는데, 100%에서 "틀렸습니다."가 나오네요 ㅠ

어느 부분에서 틀린걸까요.

import sys
input = sys.stdin.readline
# 정점과 간선 수 받기(n <= 1000, m <= 500,000)
n, m = map(int, input().split())
# 정점과 소속 리스트 생성
ver = [0]*1001
v_p = [0]*1001
v_cnt = 0
for _ in range(m):
    # 간선 정보 입력
    u, v = map(int, input().split())
    # 첫 정점 입력에 대해 정점과 소속 리스트 초기화 및 정점 카운트
    if not ver[u]:
        ver[u] = v_p[u] = u
        v_cnt += 1
    if not ver[v]:
        ver[v] = v_p[v] = v
        v_cnt += 1
    # union
    if v_p[u] != v_p[v]:
        v_p[u] = v_p[v] = min(v_p[u], v_p[v])
# 소속 리스트 정리
for i in range(1001):
    if ver[i]:
        j = i
        while j != v_p[j]:
            j = v_p[j]
        v_p[i] = j
# 등장하지 않은 정점 수 확인
hide_ver = n - v_cnt
print(len(set(v_p)) - 1 + hide_ver)

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

문제

문제

출처

ICPC

[파이썬] 어디가 틀렸을가욥? 조언을 부탁드립니다~!

gyjinro 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말