[백준 20040, 2887] - Python

취알스 8주차 기타 그래프 이론 - 5/5

20040 사이클게임

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def FindParent(parent, x):
    if parent[x] != x:
        parent[x] = FindParent(parent, parent[x])
    return parent[x]

def UnionParent(parent, x, y):
    x = FindParent(parent, x)
    y = FindParent(parent, y)
    if x>y:
        parent[x] = y
    else:
        parent[y] = x

n, m = map(int, input().split())
parent = [0]* (n+1)
game = [[] for i in range(m)]
for i in range(n+1):
    parent[i] = i
flag = 0
result = 1
for i in range(m):
    a, b = map(int, input().split())
    game[i] = [a, b]

for i in range(m):
    a, b = game[i]
    if FindParent(parent, a) == FindParent(parent, b):
        flag=1
        break
    else:
        UnionParent(parent, a, b)
        result += 1

if flag==0 and result==m+1:
    result = 0
print(result)

2887 행성 터널

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

def FindParent(parent, x):
    if parent[x] != x:
        parent[x]= FindParent(parent, parent[x])
    return parent[x]

def UnionParent(parent, a, b):
    a = FindParent(parent, a)
    b = FindParent(parent, b)
    if a > b:
        parent[a] = b
    else:
        parent[b] = a

n = int(input())
parent = [0] * (n+1)
for i in range(n+1):
    parent[i] = i
result = 0
nodes = []
edges = []
for i in range(n):
    a, b, c = map(int, input().split())
    nodes.append((i,a,b,c))

sortedbyx = sorted(nodes, key=lambda node: node[1])
sortedbyy = sorted(nodes, key=lambda node: node[2])
sortedbyz = sorted(nodes, key=lambda node: node[3])

for i in range(n-1):
    edges.append((abs(sortedbyx[i][1]-sortedbyx[i+1][1]), sortedbyx[i][0], sortedbyx[i+1][0]))
    edges.append((abs(sortedbyy[i][2]-sortedbyy[i+1][2]), sortedbyy[i][0], sortedbyy[i+1][0]))
    edges.append((abs(sortedbyz[i][3]-sortedbyz[i+1][3]), sortedbyz[i][0], sortedbyz[i+1][0]))

edges.sort()
for edge in edges:
    cost, a, b = edge
    if FindParent(parent, a) != FindParent(parent, b):
        UnionParent(parent, a, b)
        result += cost
print(result)