[백준/22954] 그래프 트리 분할 (Python)

Problem : https://www.acmicpc.net/problem/22954

22954번: 그래프 트리 분할

 

Difficulty : Gold 1

 

Status : Solved

 

Time : 00:33:31

 

---

 

문제 설명

 

 

정점 N개, 간선 M개의 그래프가 주어진다.
각 정점은 1부터 N까지 번호가 매겨져 있고, 간선도 입력되는 순서대로 1부터 M까지 번호가 매겨져 있다.
그래프에서 원하는 만큼 간선을 삭제해, 서로 다른 크기의 트리 2개로 분할해보자!
각각의 트리는 하나 이상의 정점을 가지고 있어야 하며, 두 트리가 동일한 정점이나 간선을 공유해서는 안 된다.

 

 

입력 및 출력

 

입력

 

첫 번째 줄에 정점의 개수 N, 간선의 개수 M이 주어진다. (1 <= N <= 100,000, 0 <= M <= 200,000)
두 번째 줄부터 M줄에 걸쳐서 간선을 나타내는 정수 u와 v가 주어진다. (1 <= u, v <= N, u != v)
이는 u번 정점과 v번 정점을 잇는 양방향 간선이 존재함을 나타낸다. 중복 간선은 주어지지 않는다.

 

출력

 

그래프를 분할할 수 없다면 첫 번째 줄에 -1을 출력하고 종료한다.
분할 할 수 있는 방법이 존재한다면, 아무거나 하나, 아래와 같은 형식으로 출력한다.
첫 번째 줄에 두 트리의 크기 N_1, N_2을 출력한다. (N_1과 N_2는 서로 다른 양의 정수이고, N_1 + N_2 = N을 만족해야 한다.)
두 번째 줄에는 첫 번째 트리에 속한 정점 N_1개의 번호를 출력한다.
세 번째 줄에는 첫 번째 트리에 속한 간선 N_1 - 1개의 번호를 출력한다.
네 번째 줄에는 두 번째 트리에 속한 정점 N_2개의 번호를 출력한다.
다섯 번째 줄에는 두 번째 트리에 속한 간선 N_2 - 1개의 번호를 출력한다.

출력한 트리 각각은 연결 그래프이고, 동일한 정점이나 간선을 공유해서는 안된다.

출력하는 모든 정점의 번호는 1이상 N이하를, 간선의 번호는 1이상 M이하를 만족해야 한다.

 

입력 예시

 

5 5
1 2
1 3
2 3
3 4
4 5

 

출력 예시

 

3 2
1 2 3
1 2
4 5
5

 

 

---

 

풀이

 

우선 몇 가지를 체크해 보자.

 

• N <= 2라면, 다른 크기의 트리 두개로 나눌 수 없다. N =1이면 애초에 트리가 1개이며, N == 2이면 크기가 1인 두 트리로 나눌 수밖에 없다.
• N을 다른 크기의 N1, N2개 정점의 트리로 나눈다면, 그 트리의 정점의 개수는 N1-1, N2-1이다. 따라서 M은 (N1-1 + N2-1) = N-2보다 커야 하며, 이보다 정점의 개수가 작다면 트리 2개로 나눌 수 없다.

 

다음은 트리를 구성하는 방법이다. DFS / BFS를 사용하면 여러 역할을 동시에 수행할 수 있다.

• 노드가 속하는 그래프의 모든 노드를 구할 수 있다.
• 또한, visited 배열을 사용하는 특성상 스패닝 트리(Spanning Tree)를 구할 수 있다. 모든 탐색에 사용되는 edge를 기록하기만 하면 된다.
• 마지막으로 탐색한 노드는 무조건 트리의 리프 노드가 된다.

 

모든 방문하지 않은 점에 대해 DFS / BFS를 사용하면, 현재 주어진 점들과 간선으로 이루어진 모든 그래프와 그 그래프의 스패닝 트리를 구할 수 있다. 여기서 또 조건 분기가 발생한다.

 

• 그래프 개수가 2개 초과일 경우 : 이 경우는 서로 다른 크기의 트리 2개로 분할하는 것이 불가능하므로 -1을 출력한다.
• 그래프 개수가 2개일 경우 : 이 경우는 그래프에 속하는 노드 개수를 비교한다. 만약 노드 개수가 동일하다면 서로 다른 크기의 트리가 아니므로 -1을 출력한다. 그렇지 않다면 각 스패닝 트리의 노드 번호와 간선 번호를 전부 출력한다.
• 그래프 개수가 1개일 경우 : 단일 스패닝 트리에서 가장 간단히 2개의 트리로 나눌 수 있는 경우는, 리프 노드 하나를 때어 새로운 트리를 구성하는 것이다. 그리고 우리는 앞서 리프 노드가 보장되는  노드 번호를 구할 수 있다. 그 리프 노드와 그 노드가 포함되는 간선을 찾아 제거한다면, 우리는 주어진 점들과 간선들로 트리를 구성할 수 있다.

 

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge_list = [[i] + list(map(int, input().split())) for i in range(1, M+1)]
if N <= 2 or M <= N-3:
  print(-1)
  exit()

edge_dict = defaultdict(list)
visited = [False]*(N+1)
for i, a, b in edge_list :
  edge_dict[a].append((i, b))
  edge_dict[b].append((i, a))

def dfs(node) :
  visited[node] = True
  node_list = [node]
  edge_list = []
  q = [node]
  while q :
    node = q.pop()
    for idx, nxt in edge_dict[node] :
      if not visited[nxt] :
        visited[nxt] = True
        edge_list.append(idx)
        node_list.append(nxt)
        q.append(nxt)

  return edge_list, node_list, node

edges, nodes, last_nodes = list(), list(), list()
for i in range(1, N+1) :
  if not visited[i] :
    _edges, _nodes, _last_node = dfs(i)
    edges.append(_edges)
    nodes.append(_nodes)
    last_nodes.append(_last_node)

if len(nodes) > 2 :
  print(-1)
  exit()
if len(nodes) == 2 :
  if len(nodes[0]) == len(nodes[1]) :
    print(-1)
    exit()
  print(len(nodes[0]), len(nodes[1]))
  for i in range(2) :
    print(*nodes[i])
    print(*edges[i])
  exit()

edges, nodes, last_node = edges[0], nodes[0], last_nodes[0]
cur_edges = list()
for idx in edges :
  _, a, b = edge_list[idx-1]
  if a == last_node or b == last_node:
    continue
  cur_edges.append(idx)

print(len(nodes)-1, 1)
print(*[n for n in nodes if n != last_node])
print(*cur_edges)
print(last_node)
print()

풀이 완료!