연습문제

[한양대 HCPC 2023] 사이클 없는 그래프 만들기

난이도
Lv. 4
제출
36 명
참가자
8 명
정답률
45.45 %
지원 언어
C
C++
Java
Python
JavaScript
언어별 시간/메모리
언어별 시간/메모리 표
언어 시간 메모리
C 1초 1024MB
Java 3초 1024MB
Python 5초 1024MB
C++ 1초 1024MB
JavaScript 5초 1024MB

N개의 정점과 M개의 간선을 가진 무향 그래프 G가 주어진다. 시간 T=1일 때, G에서 정해진 K개의 정점을 지운다. T=t (1 < t)일 때는 T=t−1에서 지워진 정점과 이웃하였던 정점들을 지운다. 이때 G에 사이클이 존재하지 않는 최초의 시간 T=C를 구하는 프로그램을 작성하여라.


처음 주어지는 그래프 G는 모든 정점이 연결된 연결 그래프이며, 사이클이 존재한다. 또한 정점이 삭제되면 해당 정점과 연결된 간선도 함께 없어진다. 자기 자신과 연결된 간선은 주어지지 않으며, 중복된 간선이 주어질 수 있다.


노트:


 G의 사이클은 G의 부분그래프 중 비어있지 않고 연결되어 있으며, 모든 정점의 차수가 2인 그래프를 의미한다.

제약조건

2 ≤ N ≤ M ≤ 200,000

1 ≤ K ≤ N

입력형식

첫 번째 줄에 그래프 G의 정점의 수 N과 간선의 수 M, 시간 T=1일 때 삭제하는 정점의 수 K가 공백으로 구분되어 주어진다.

두 번째 줄부터 M개의 줄에 걸쳐 간선의 정보 u, v가 공백으로 구분되어 주어진다. 이는 u번 정점과 v번 정점이 간선으로 연결되어 있음을 의미한다. (1 ≤ u,v ≤ N; u ≠ 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

목록