일반적으로 번역 기능은 오역의 문제가 있어서 중단된 상태입니다.
이것도 오역이 매우 많아서 채택할 수 없다고 생각합니다.
- maximum cut은 "굉장히 어려운"이라는 뜻이 아닙니다.
- 재현이가 또 다른 문제를 푸는 게 아니라 내는 겁니다.
- simple graph는 그래프 이론에서 자주 쓰이는 용어인데 "간단한 그래프"라는 번역은 본 적이 없습니다.
- subset은 수학에서 거의 항상 쓰이는 용어인데 "하위 집합"이라는 번역은 본 적이 없습니다.
- bipartite는 "두 부분"이라는 뜻이 아닙니다.
- 세 번째 조건은 직접 읽어보셔도 매우 이상하다는 것을 알 수 있습니다.
nothanjae 3년 전 1
과연 이 번역이 반영될 것인지....
문제이름:Koosaga's problem(그대로 두는게 나을것 같네요.)
재현이는 Petrozavodsk 겨울 2019 캠프에서 그래프 문제중 굉장히 어려운 문제를 해결했다. 재현이는 그래서 같은 성격의 또 다른 문제를 풀어 당신을 기쁘게 하기로 결정했습니다.
N개의 꼭짓점과 M개의 모서리가 있는 간단한 연결된 그래프 G=(V,E) 가 나옵니다. 다음과 같은 간선 S⊆E의 하위 집합의 개수를 찾아야 합니다.
-S에서 간선을 제거하면 그래프가 두 부분으로 나뉩니다.
-|S|≤2
-|T|와 같은 다른 부분 집합 T⊆E는 존재하지 않습니다. (처음 2개의 조건은 유지되며, S는 비워 둘 수 있습니다.
입력:입력의 첫번째 줄에는 두 개의 정수 N과 M이 주어집니다. (3≤N≤250000,N-1≤M≤250000)
그런 다음 M 개의 줄이 이어집니다. 각각의 줄은 공백으로 구분된 두 개의 정수 u i 및 v i (1 ≤ u i , v i ≤ N)가 주어집니다. 정점 u i와 정점 v i를 연결하는 양방향 간선을 설명합니다.
주어진 그래프에 루프(계속 돌아가는 부분) 이나 다중 간선이 없고 그래프가 연결되어 있음이 보장됩니다.
출력: 주어진 조건을 만족하는 부분 집합의 수를 구합니다.