[그래프의 줄기/G2/Python3]

24461번 그래프의 줄기 G2

 

문제
그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 0이 아닌 경로이다. 사이클이 존재하지 않는 그래프가 주어진다.우리는 이 그래프의 정점 중에서 연결된 간선이 하나인 정점을 가장자리 정점이라고 정의하자.이 그래프의 가장자리 정점을 동시에 없애는 행동을 반복하면서, 그래프가 일직선의 모양이 되면 남아있는 정점의 집합을 그래프의 줄기라고 정의하자. 단, 가장자리 정점의 개수가 둘 이하라면 그래프가 일직선 모양이라고 한다. 위 그림과 같은 그래프가 있다고 할 때, 아래와 같이 가장자리 정점과 연결된 간선을 빨간색으로 표시하면 아래와 같다. 빨간색 간선과 연결된 가장자리 정점의 연결을 끊으면 아래 그림과 같이 일직선 모양으로 연결된 그래프의 줄기가 남는다. 만약 그래프가 일직선 모양이 되었다면, 가장자리 정점이 더 존재하더라도 더 이상 가장자리 정점들을 없애지 않는다.이때 그래프의 줄기를 이루는 정점을 구하는 프로그램을 작성하시오.

입력
입력의 첫 번째 줄에는 처음 그래프의 정점의 수 N이 주어진다. (2≤N≤100000)
이후 N−1줄에 걸쳐 각 간선으로 연결된 두 정점의 번호 a, b가 입력된다. (0≤a, b<N, a≠b)

출력
출력의 첫 번째 줄에 그래프의 줄기를 이루는 정점의 번호들을 오름차순으로 정렬하고 공백으로 구분하여 출력한다.

 

 

그래프 이론, 방향 비순환 그래프, 위상 정렬

 

위상 정렬을 이용하여 풀이하였다.

각 정점은 연결된 간선의 개수를 저장한다.

 

연결된 간선이 1인 가장자리 정점을 제거하면서 제거된 정점이 가장자리 정점이 되는지 확인했다.

기저조건인 가장자리 정점의 개수가 2 이하인 경우를 지속적으로 확인했다.

 

 

 

import sys
n = int(sys.stdin.readline())

routes = [[] for _ in range(n)]
cnts = [0] * (n)
removed = [False] * (n)

for _ in range(n-1):
    v1, v2 = map(int, sys.stdin.readline().split())
    routes[v1].append(v2)
    routes[v2].append(v1)
    cnts[v1] += 1
    cnts[v2] += 1

edge_v = []

for i in range(n):
    if cnts[i] == 1: edge_v.append(i)

while len(edge_v) > 2:
    next_edge_v = []
    for v in edge_v:
        removed[v] = True
        for vv in routes[v]:
            if removed[vv]: continue
            cnts[vv] -= 1
            if cnts[vv] == 1: next_edge_v.append(vv)
    edge_v = next_edge_v


result = []
for i in range(n):
    if not removed[i]: result.append(i)

print(*result)

 

---