33722번 - [B] 이진 매칭 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 73 | 54 | 32 | 66.667% |
문제
하이바이는 최근 이진 매칭을 배웠다. 이진 매칭이 무엇인지 모른다면, 아래 정의를 참고하자.
무방향 그래프 $G=(V,E)$의 이진 매칭은 아래 조건을 만족하는 $S\subseteq E$이다.
- $S$에 속한 간선들만 남긴 그래프 $G'=(V,S)$에서, 모든 정점 $v$에 대해 $\mathrm{deg}(v)\equiv 1\pmod 2$이다. 여기서 $\mathrm{deg}(v)$는 $v$의 차수를 의미한다.
마침 출제할 만한 문제가 없었던 하이바이는 주어진 그래프의 이진 매칭을 찾는 문제를 내기로 했다. 그런데 실수로 입력 제한을 $106$이 아니라 $10^6$으로 세팅해 버렸다!
입력
첫째 줄에는 그래프 $G$의 정점 개수 $N$과 간선 개수 $M$이 공백으로 구분되어 주어진다. $(1\le N\le 10^6;$ $0\le M\le 10^6)$
이후 $M$개의 줄에 걸쳐 $i+1$번째 줄에는 $2$개의 정수 $v_i$, $w_i$가 공백으로 구분되어 주어진다. 이는 $v_i$번 정점과 $w_i$번 정점을 연결하는 $i$번 간선을 의미한다. $(1\le v_i,w_i\le N;$ $v_i\neq w_i)$
두 정점을 잇는 간선이 여러 개일 수 있으며, 주어지는 그래프가 연결되어 있지 않을 수도 있다.
출력
만약 주어진 그래프의 이진 매칭이 존재하지 않는다면 첫째 줄에 -1을 출력한다.
만약 주어진 그래프의 이진 매칭이 존재한다면 첫째 줄에 이진 매칭의 크기 $K$를 출력하고, 둘째 줄에 이진 매칭에 속한 간선의 번호를 오름차순으로 공백으로 구분하여 출력한다.
가능한 이진 매칭이 여러 가지라면 그중 아무거나 하나를 출력하면 된다. 이진 매칭의 크기를 최대화하거나, 최소화할 필요는 없다.
예제 입력 1
6 7 1 2 2 3 3 4 4 1 1 3 5 6 6 5
예제 출력 1
3 1 3 6
예제 입력 2
3 3 1 2 1 3 2 3
예제 출력 2
-1
예제 입력 3
4 1 2 3
예제 출력 3
-1
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: minjunnick, mujigae, pyb1031, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호