머리와 발이라는 두 가지 유형의 정점이 있는 특별한 유형의 그래프가 있다고 가정합니다. 그래프에는 머리가 하나만 있고 머리를 각 발에 연결하는 k 개의 모서리가 있습니다. 무향, 무가중 그래프가 주어진다면; 우리는 그래프의 꼭짓점 disjoint subgraphs에서 이러한 특별한 유형의 그래프를 찾아야 합니다. 두 그래프에 공통 정점이 없는 경우 이 그래프는 분리된 정점이라고 합니다.
따라서 입력이 다음과 같으면
노드 수(n) =5, 피트 수(t) =2이면 출력은 5가 됩니다.
주어진 그래프의 정점 분리 하위 그래프인 5개의 특수 그래프가 있을 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- G :=n+1개의 빈 목록을 포함하는 새 목록
- 가장자리의 각 항목에 대해 다음을 수행합니다.
- :=항목[0]
- d :=항목[1]
- G[s] 끝에 d 삽입
- G[d] 끝에 s 삽입
- 방문:=새 지도
- 0에서 n 사이의 i에 대해
- v :=지[i]
- v의 크기가 1과 같으면
- :=v[0]
- 방문 시 s가 없으면
- 방문[s] :=[i]
- 그렇지 않으면
- 방문 끝에 i 추가
- 그렇지 않으면 v의 크기가 0과 같을 때
- n :=n - 1
- tmp :=0
- 방문 시 k마다 다음을 수행합니다.
- x :=방문 크기[k] -t
- x> 0이면
- tmp :=tmp + x
- n - tmp를 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(n, t, edges):
G = [[] for _ in range(n + 1)]
for item in edges:
s, d = map(int, item)
G[s].append(d)
G[d].append(s)
visit = {}
for i in range(n):
v = G[i]
if len(v) == 1:
s = v[0]
if s not in visit:
visit[s] = [i]
else: visit[s].append(i)
elif len(v) == 0:
n -= 1
tmp = 0
for k in visit:
x = len(visit[k])-t
if x > 0:
tmp += x
return n - tmp
print(solve(6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]))
입력
6, 2, [(1,4), (2,4), (3,4), (3,4), (5,3), (6,3)]
출력
5