30870번 - 사이클 없는 그래프 만들기 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 382 | 137 | 116 | 35.913% |
문제
$N$개의 정점과 $M$개의 간선을 가진 무향 그래프 $G$가 주어진다. 시간 $T=1$일 때, $G$에서 정해진 $K$개의 정점을 지운다. $T=t\ (1 < t)$일 때는 $T=t-1$에서 지워진 정점과 이웃하였던 정점들을 지운다. 이때 $G$에 사이클이 존재하지 않는 최초의 시간 $T=C$를 구하는 프로그램을 작성하여라.
처음 주어지는 그래프 $G$는 모든 정점이 연결된 연결 그래프이며, 사이클이 존재한다. 또한 정점이 삭제되면 해당 정점과 연결된 간선도 함께 없어진다. 자기 자신과 연결된 간선은 주어지지 않으며, 중복된 간선이 주어질 수 있다.
입력
첫 번째 줄에 그래프 $G$의 정점의 수 $N$과 간선의 수 $M$, 시간 $T=1$일 때 삭제하는 정점의 수 $K$가 공백으로 구분되어 주어진다. $(2\le N\le M\le 200\, 000;$ $1\le K\le N)$
두 번째 줄부터 $M$개의 줄에 걸쳐 간선의 정보 $u, v$가 공백으로 구분되어 주어진다. 이는 $u$번 정점과 $v$번 정점이 간선으로 연결되어 있음을 의미한다. $(1\le u,v\le N;$ $u \ne v)$
그 다음 줄에는 $T=1$일 때 삭제하는 정점의 번호 $K$개가 공백으로 구분되어 주어진다.
출력
첫 번째 줄에 $T=C$에서 정점을 지우고 처음으로 사이클이 존재하지 않게 되었을 때의 시간 $C$를 출력한다.
예제 입력 1
7 8 1 1 2 2 3 2 5 3 4 4 5 4 6 5 6 6 7 3
예제 출력 1
2
예제 입력 2
4 4 3 1 2 2 3 3 4 4 1 1 2 4
예제 출력 2
1
노트
$G$의 사이클은 $G$의 부분그래프 중 비어있지 않고 연결되어 있으며, 모든 정점의 차수가 $2$인 그래프를 의미한다.
출처
University > 한양대학교 > 제10회 한양대학교 프로그래밍 경시대회(HCPC) > Beginner Division C번
- 문제를 만든 사람: my3
- 문제를 검수한 사람: andrewmjk1, cologne, hjroh0315, mjhmjh1104, naeby, seonah, solvedac, yijw0930
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호