8. 기타 그래프 알고리즘 예제 3문제 (팀 결성, 도시 분할 계획, 커리큘럼)

팀 결성(union - find)

n명의 학생이 있다

두 학생의 팀을 합치는 연산과

두 학생의 같은 팀 여부를 확인하는 연산이 있다

입력받아서 연산하고~ 같은팀 여부 확인 연산은 같은팀일 시 Yes, 아닐 시 No 출력

import sys
input=sys.stdin.readline


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

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

n,m=map(int,input().split())#학생n명, 연산m번

parent=[0]*(n+1)
for i in range(n+1):
    parent[i]=i
    
for i in range(m):
    data=list(map(int,input().split()))
    if data[0]==0:
        union_parent(parent,data[1],data[2])
    if data[0]==1:
        a=find_parent(parent,data[1])
        b=find_parent(parent,data[2])
        if a==b:
            print("YES")
        else:
            print("NO")

---

도시 분할 계획(크루스칼)

도시를 두 마을로 분할하려고 한다

각각의 마을 내에서는 모든 집이 도로로 연결되어 있어야 하고, 마을과 마을은 연결되지 않아도 된다

도로 건설 비용을 최소화하고 그 비용을 출력하라

입력:

첫 줄 n,m (도시개수, 지을 수 있는 도로개수)

이후 m줄에 걸쳐 a,b,cost를 입력받음 (a=도시1, b=도시2, cost=도시 1과 2를 잇는 도로의 건설비용 )

 

import sys
input=sys.stdin.readline

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

def union_parent(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

n,m=map(int,input().split())
parent=[x for x in range(n+1)]
print(parent)
edges=[]
for i in range(m):
    a,b,cost=map(int,input().split())
    edges.append((cost,a,b))

edges.sort()#비용 순 정렬

MAX_cost=0
result=0
for edge in edges:
    cost,a,b=edge
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a!=b:
        union_parent(parent,a,b)
        result+=cost
        MAX_cost=max(MAX_cost,cost)

print(result-MAX_cost)

 

---

커리큘럼(위상정렬)

n개의 강의가 있다

각각의 강의를 듣기 위한 선수강강의가 존재한다

각각의 강의를 듣기 위한 최소 시간은?

import copy
import sys
from collections import deque

input=sys.stdin.readline

n=int(input())
times=[0]*(n+1)
graph=[[]for i in range(n+1)]
indegree=[0]*(n+1)
for i in range(1,n+1):
    data=list(map(int,input().split()))
    times[i]=data[0]
    for j in data[1:-1]:
        graph[j].append(i)
        indegree[i]+=1


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

topology_sort()