[백준] 22954. 그래프 트리 분할

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

요약

• 그래프가 주어짐
• 간선을 적절히 제거해서 두개의 트리로 분리(공유하는 것이 없도록 분리)
• 트리의 크기가 서로 달라야함
• 분리가 된다면 정보를 출력

접근법

• 그래프에서 트리 구성(union-find) -> 그룹 개수 파악 -> 그룹별 노드 구분 -> 간선 출력
• 그래프에서 트리를 잘 만들어 본다면 할 일이 보일 것 같음
  • 트리를 만들 때는 union-find 사용
    • 어떤 간선이 사용되었는지 체크
    • 노드별 인접 간선이 몇 개인지 체크
  • 하나의 트리가 만들어진다면? 적절히 간선을 제거해서 두개로 나눔
    • 노드 1 vs 노드 n - 1로 나눔
    • 인접간선이 1개인 노드와 나머지 노드로 나누면 편함
  • 두 개의 트리가 만들어진다면?
    • 각각의 크기를 판단함
      • 같으면 : 실패
      • 다르면 : 정보를 기억함
  • 세 개 이상의 트리가 만들어진다면? 실패
• 두 개의 트리를 출력하는 방법
  • 그래프 -> 트리 구성에 사용한 간선을 체크함
  • 그룹 1과 그룹 2에 속하는 노드를 체크함
  • 그룹의 크기 출력은 쉬움
  • 간선의 출력은 전체 간선을 훑으면서
    • 간선이 트리를 구성하는데 사용했고
    • 간선의 양 끝점 모두가 해당 그룹에 속하면
    • 그룹에 속하는 간선이라고 판단