[백준 1717, 1922, 2252] - Python

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

1717 집합의 표현

크루스칼 알고리즘을 이용한다.

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,m = map(int, input().split())
parent = [0] * (n+1)
for i in range(n+1):
    parent[i] = i

for i in range(m):
    a, b, c = map(int, input().split())
    if a == 0:
        UnionParent(parent, b, c)
    else:
        if FindParent(parent, b) == FindParent(parent, c):
            print("YES")
        else:
            print("NO")

1922 네트워크 연결

크루스칼 알고리즘 문제

import sys
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())
m = int(input())
parent = [0] * (n+1)
edges = []
result = 0

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

for i in range(m):
    a, b, c = map(int, input().split())
    edges.append((c,a,b))

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)

2252 줄세우기

기본 위상정렬 문제

from collections import deque

v, e = map(int, input().split())
indegree = [0]*(v+1)
graph = [[] for i in range(v+1)]

for _ in range(e):
    a, b = map(int, input().split())
    graph[a].append(b)
    indegree[b] += 1

def topology_sort():
    result=[]
    q = deque()
    for i in range(1, v+1):
        if indegree[i]==0:
            q.append(i)
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] ==0:
                q.append(i)
    for i in result:
        print(i, end=' ')

topology_sort()