17304번 - 변호사들 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 512 MB | 584 | 113 | 97 | 25.594% |
문제
N명의 변호사가 사기 범죄를 저지른 혐의로 기소되었다. N명의 변호사는 서로를 변호하여 전원 무사히 무죄로 처리되려고 한다.
변호사들은 자신이 신뢰하는 변호사에게만 변호를 받을 수 있다. 이 신뢰관계란 M개의 (A, B)쌍으로 표현되는데, 이는 변호사 B가 변호사 A를 신뢰한다는 의미로 이 경우에만 변호사 A가 변호사 B를 변호할 수 있다.
각각의 변호사들의 실력은 매우 뛰어나기 때문에, 1명 이상의 변호를 받은 사람은 무조건 무죄가 된다. 단, 두 변호사 A, B에 대해 A가 B를 변호하고, B가 A를 변호하는 경우는 매우 수상하기 때문에 둘 모두 유죄가 된다.
각 (A, B) 쌍에 대해 변호사 A가 변호사 B를 변호할지 말지를 선택하여 모든 변호사가 무죄가 되는 것이 가능한지 판정하라.
입력
첫 줄에 N과 M이 주어진다. (1 ≤ N, M ≤ 200,000)
두 번째 줄부터 M 줄에 걸쳐 i번째 줄에는 서로 다른 두 정수 Ai, Bi가 주어진다. 이는 변호사 Ai가 변호사 Bi를 변호할 수 있다는 뜻이다.
주어지는 입력에서 순서쌍 (A, B)가 중복하여 나타나는 경우는 없다.
출력
모든 변호사가 1명 이상의 변호를 받고, 서로를 변호하는 변호사 쌍이 없도록 할 수 있는 경우 첫 줄에 YES을 출력한다.
불가능한 경우 첫 줄에 NO를 출력한다.
예제 입력 1
3 3 1 2 2 3 3 1
예제 출력 1
YES
예제 입력 2
4 6 1 2 1 3 1 4 2 3 2 4 3 4
예제 출력 2
NO
예제 입력 3
4 4 1 2 2 1 3 4 4 3
예제 출력 3
NO
출처
University > 경인지역 6개대학 연합 > shake! 2019 E번
Camp > Petrozavodsk Programming Camp > Winter 2023 > Day 2: GP of ainta B번
- 문제를 만든 사람: ainta
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호