[Good Bye, BOJ 2020!]C.양분(미완성)

이마 탁!

 

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

20530번: 양분

 

 

 

1. 트리에서 쿼리는 1이다.
2. 트리에서 간선 하나만 추가되었다.
3. 나올 수 있는 경우는 1 아니면 2이다. 
-> 사이클을 알아내서 그 간선을 지나간다면 2 아니면 1 출력한다.

그래프로 입력을 받을 때, 도착 노드에 1씩 더해 준다.(그래프에 방향이 있다고 생각한다.)

그렇게 한다면 루트와 사이클 도착점을 알 수 있었다.

n, q = map(int, input().split())
field = {}
nums = [0 for _ in range(n + 1)]
 
for _ in range(n):
    a,b = map(int, input().split())
    nums[b] += 1
    if a not in field:
        field[a] = [b]
    elif b not in field[a]:
        field[a].append(b)
 
nums[0] = 1
root = nums.index(min(nums))
cycle = nums.index(max(nums))