b개의 노드와 많은 모서리의 무방향 그래프가 있다고 가정합니다. 이 그래프에서 오일러 회로를 구축하는 데 필요한 최소 간선을 찾아야 합니다.
따라서 입력이 다음과 같으면
그러면 출력은 1이 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- dfs() 함수를 정의합니다. g, 방문, odd_vert, degree, comp, v 가 필요합니다.
- 방문[v] :=1
- 도[v] mod 2가 1과 같으면
- odd_vert[comp] :=odd_vert[comp] + 1
- 0에서 g[v]까지의 범위에 있는 u에 대해
- 방문[u]이 0과 같으면
- dfs(g, 방문, odd_vert, 정도, comp, u)
- 방문[u]이 0과 같으면
- 메인 방법에서 다음을 수행하십시오 -
- g :=n+1개의 빈 목록 목록
- :=새 목록
- :=새 목록
- degree :=크기의 새 목록(n + 1) 및 0으로 채우기
- 방문:=크기의 새 목록(n + 1) 및 0으로 채우기
- odd_vert :=크기(n + 1) 및 채우기의 새 목록
- 0 포함
- 0~m 범위의 i에 대해
- g[s[i]] 끝에 d[i] 삽입
- g[d[i]] 끝에 s[i] 삽입
- 도[s[i]] :=도[s[i]] + 1
- 도[d[i]] :=도[d[i]] + 1
- ans :=0, comp :=0
- 1에서 n + 1 사이의 i에 대해 다음을 수행합니다.
- 방문[i]이 0과 같으면
- comp :=comp + 1
- dfs(g, 방문, odd_vert, 정도, comp, i)
- odd_vert[comp]가 0과 같으면
- e 끝에 comp 삽입
- 그렇지 않으면
- o 끝에 comp 삽입
- 방문[i]이 0과 같으면
- o의 크기가 0과 같고 e의 크기가 1과 같으면
- 0을 반환
- o의 크기가 0과 같으면
- e의 반환 크기
- e의 크기가 0과 같지 않으면
- ans :=as + e의 크기
- 0에서 o까지의 범위에 있는 i에 대해 다음을 수행합니다.
- ans :=ans + odd_vert[i] / 2(정수 부분만 사용)
- 반환
예
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def dfs(g, visit, odd_vert, degree, comp, v): visit[v] = 1 if (degree[v] % 2 == 1): odd_vert[comp] += 1 for u in range(len(g[v])): if (visit[u] == 0): dfs(g, visit, odd_vert, degree, comp, u) def solve(n, m, s, d): g = [[] for i in range(n + 1)] e = [] o = [] degree = [0] * (n + 1) visit = [0] * (n + 1) odd_vert = [0] * (n + 1) for i in range(m): g[s[i]].append(d[i]) g[d[i]].append(s[i]) degree[s[i]] += 1 degree[d[i]] += 1 ans = 0 comp = 0 for i in range(1, n + 1): if (visit[i] == 0): comp += 1 dfs(g, visit, odd_vert, degree, comp, i) if (odd_vert[comp] == 0): e.append(comp) else: o.append(comp) if (len(o) == 0 and len(e) == 1): return 0 if (len(o) == 0): return len(e) if (len(e) != 0): ans += len(e) for i in range(len(o)): ans += odd_vert[i] // 2 return ans b = 3 a = 2 source = [ 1, 2 ] destination = [ 2, 3] print(solve(b, a, source, destination))
입력
b = 3 a = 2 source = [ 1, 2 ] destination = [ 2, 3]
출력
1