https://www.acmicpc.net/problem/17834
사이클이 0개이거나 사이클의 오솔길 개수가 짝수개인 경우에만 영원히 만나지 못하는 상황이 생김.
영원히 만나지 못하려면 사자와 토끼 사이에 오솔길이 홀수개만큼 떨어져있어야함.
사이클 탐지 해서 그 길이가 짝수인지 먼저 판별하고
사자와 토끼 사이에 오솔길이 1개인 경우 모두 찾기 => 오솔길의 개수 x 2
3개 이상인 경우는 어떻게 찾지.
사이클 찾기
사이클을 찾기 위해서 생각나는 방법인 union-find를 사용하기로 했다.
def find(x, parent):
if x != parent[x]:
find(parent[x], parent)
return parent[x]
def union(a, b, parent):
pa = find(a, parent)
pb = find(b, parent)
if pa != pb:
parent[pb] = pa
return True
else:
False
막상 코드를 짜고 나니까 만약 사이클이 붙어있다면, 몇 개의 오솔길을 공유하는 사이클이 있다면 이 방법으로 탐지할 수 있을 지 의문이 들었다. 그리고 사이클을 찾더라도 개수 세는 것이나 거리에 따라 발생할 수 있는 경우를 찾는 구현을 하는 방법을 모르겠어서 결국 다른 글을 찾아보았다.
1707
어떤 글에서는 이 문제가 1707번 문제의 연장선이라고 했다. 그래서 먼저 풀어보았다.
일단 안 잡히는 오솔길 모양을 판별할 수는 있게 되었다. 안 잡히는 경우는 그러면 서로 다른 색깔의 위치에서 시작하면 되는 거인 것 같다.
코드 2 - 실패
from collections import defaultdict
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
road = defaultdict(list)
for _ in range(m):
a, b = map(int, input().split())
road[a].append(b)
road[b].append(a)
que = [(1, 0)]
idx = 0
visited = [-1 for _ in range(n+1)]
chk = True
for i in range(1, n+1):
if visited[i] == -1 and chk:
visited[i] = 0
que = [(i, 0)]
idx = 0
while idx < len(que) and chk:
now, color = que[idx]
idx += 1
for next in road[now]:
if visited[next] == -1:
que.append((next, abs(color-1)))
visited[next] = abs(color-1)
elif visited[next] == visited[now]:
chk = False
break
if chk:
print(n**2 // 2)
else:
print(0)오솔길이 모두 연결되어 있다는 조건이 없어서 1707의 코드를 그대로 가져왔다. 모든 점에 대해서 BFS를 돌면서 이분 그래프인지 확인하였다.
결과는 점의 개수 ^ 2 / 2를 했는데 당연하게도 이분 그래프니까 색깔의 배분이 절반이 될 것이라고 생각했는데 점이 3개인 경우도 있을 수 있기에 한 점만 공유하고 나머지는 다 떨어져있는 별 모양 같은 경우도 있을 수 있는데 간과했다.
visited를 돌면서 1이 적힌 점의 숫자를 세고 (n - 1의 개수) * (1의 개수)해준 뒤 서로 위치가 뒤 바뀔 수도 있기에 2를 곱해주었다.
