[Baekjoon] 20530번 : 양분

1. 문제

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

• 트리, DFS 문제

// 문제
나무 T는 양분을 먹고 자란다.

원래 나무는 정점 N개와 간선 N-1개로 구성되어야 하지만, 
양분을 너무 많이 먹어버린 나머지 나무 T는 N개의 간선을 갖게 되었다. 
더 이상 트리가 아니기 때문에 T는 꿈의 무대인 트리와 쿼리에 등장하지 못한다. 
슬퍼하고 있는 T를 위해 정휘는 새로운 문제를 만들어 주었다.

N개의 정점과 N개의 간선으로 이루어진 연결 그래프 T가 주어진다. 
정점은 1번부터 N번까지 번호가 매겨져 있고, 
간선도 1번부터 N번까지 번호가 매겨져 있다. 
아래 쿼리를 수행하는 프로그램을 작성하시오.

u v : u번 정점에서 v번 정점으로 가는 단순 경로의 수를 출력한다.

// 입력
첫째 줄에 두 자연수 N, Q가 주어진다. 
주어지는 그래프의 정점과 간선의 개수가 N개이며 
쿼리가 Q개 주어진다는 것을 의미한다.

둘째 줄부터 N개의 줄에는 i번 간선이 연결하는 두 정점 번호 a, b가 주어진다.
다음 Q개 줄에는 쿼리가 한 줄에 하나씩 주어진다.

// 출력
각각의 쿼리마다 한 줄에 하나씩 결과를 출력한다.

// 제한
1 <= N, Q <= 200000 
1 <= a, b, u, v <= N
a != b
u != v 
입력으로 주어진 그래프 T는 중복 간선과 
자기 자신으로 향하는 간선이 없는 연결 그래프다.

// 예제 입력 1 
7 2
1 2
1 3
2 4
2 5
3 6
3 7
2 3
2 4
4 5

// 예제 출력 1 
1
1

2. 핵심 아이디어

3. Python 문제풀이

import sys
sys.setrecursionlimit(300000)
input = sys.stdin.readline

def go(now, base) :
  while now != base :
    is_cycle[now] = True
    now = parent[now]
  is_cycle[base] = True

def dfs(now, prev) :
  check[now] = True
  for i in adj[now] :
    if i == prev :
      continue
    if not check[i] :
      parent[i] = now
      res = dfs(i, now)
      if res :
        return res
    elif not fin[i] :
      go(now, i)
      return True
  fin[now] = True
  return False

def get_tree_num(now, prev) :
  tr_num[now] = num
  for i in adj[now] :
    if i == prev :
      continue
    if is_cycle[i] :
      continue
    if tr_num[i] == -1 :
      get_tree_num(i, now)

n, q = map(int, input().split())

adj = [[] for _ in range(n+1)]
is_cycle = [False] * (n + 1)
check = [False] * (n + 1)
fin = [False] * (n + 1)
parent = [-1] * (n + 1)

for i in range(1, n+1) :
  a, b = map(int, input().split())
  adj[a].append(b)
  adj[b].append(a)

dfs(1, -1)
tr_num = [-1] * (n + 1)
num = 0
for i in range(1, n+1) :
  if is_cycle[i] :
    get_tree_num(i, -1)
    num += 1

for _ in range(q) :
  a, b = map(int, input().split())
  if tr_num[a] == tr_num[b] :
    print(1)
  else :
    print(2)

4. Java 문제풀이