백준(BOJ) 20530 양분(Python)

문제 내용.

 

DFS 문제.

일반적인 트리에서는 u번 정점에서 v번 정점으로 가는 단순 경로가 1개 존재한다.

그러나 트리에 하나의 간선이 추가되면, 이 때는 이야기가 달라진다.

트리에 하나의 간선이 추가됨으로써 그래프 내에는 반드시 하나의 사이클이 발생한다.

사이클이 발생하게 되면 해당 사이클을 기점으로 단순 경로의 개수에 변화가 생긴다.

사이클 위에 있는 정점은 모두 사이클을 도는 두 가지의 방향에 따라 단순 경로가 생기고, 그 외에도 사이클 위에 있는 정점에서 다른 사이클 위에 있는 정점과의 간선을 제거해 얻을 수 있는 각 트리 간의 단순 경로 역시 2개이다.

즉, 사이클 위에 있는 각 정점에서 다른 사이클 위에 있는 정점과의 간선을 제거해 얻을 수 있는 트리들을 구하고, 각 쿼리마다 들어오는 정점들이 서로 다른 트리에 속해있는 경우에는 2개, 같은 트리에 속해있는 경우에는 1개의 단순 경로를 얻을 수 있게 된다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import bisect
import math
from itertools import product
from itertools import combinations
"""
from itertools import combinations
from itertools import combinations_with_replacement
from itertools import permutations
import copy
"""
input=sys.stdin.readline
#print=sys.stdout.write
sys.setrecursionlimit(100000000)

def find_cycle(x,y):
    for i in L[x]:
        if i!=y:
            if not visited[i]:
                visited[i]=1
                parent[i]=x
                k=find_cycle(i,x)
                if k:
                    return k
            else:
                return [i,x]
    return 0

def dfs(x,y):
    for i in L[x]:
        if not cycle[i] and not visited[i]:
            visited[i]=1
            parent[i]=y
            dfs(i,y)

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

parent=[i for i in range(n+1)]
L=[[] for _ in range(n+1)]
visited=[0 for i in range(n+1)]
cycle=[0 for i in range(n+1)]

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

visited=[0 for i in range(n+1)]
visited[1]=1
a,b=find_cycle(1,0)

while a!=b:
    cycle[b]=1
    b=parent[b]
cycle[a]=1

visited=[0 for i in range(n+1)]
for i in range(1,n+1):
    if cycle[i]:
        visited[i]=1
        parent[i]=i
        dfs(i,i)

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

유니온 파인드처럼 풀다가 계속 틀려서 결국 DFS로 풀었다.