34133번 - [A] Artistic Graph Coloring Task 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 29 | 17 | 16 | 59.259% |
문제
히바이는 새로운 예술 작품을 만들기로 했다. 모든 예술 작품에 의미를 담는 히바이는 다음과 같은 생각을 담아 예술 작품을 만들기로 했다.
- 이번 예술 작품은 “모든 것에는 순서가 있고 흐름이 있다”는 것을 담는 방향 비순환 그래프를 기반으로 한다.
- 또한, “모든 것에는 저마다의 색이 있다”는 점을 담아 그래프의 각 정점에 색깔을 칠할 것이다.
- 여기에, “세상에는 어떻게 보아도 새로운 것들이 넘쳐난다”는 점을 담아 그래프 위의 임의의 경로에 대해 해당하는 경로 위의 모든 정점의 색깔을 다르게 칠할 것이다.
- 마지막으로, “그럼에도 넓게 보면 생각보다 비슷한 것들은 많다”는 점을 담아 사용하는 색깔의 개수를 최소화할 것이다.
방향 비순환 그래프가 주어질 때, 히바이가 위와 같은 생각을 담아 정점을 칠한다면 최소 몇 개의 색깔을 사용해야 하는지 구해보자.
입력
첫째 줄에는 방향 비순환 그래프의 정점 개수 $N$과 간선 개수 $M$이 공백으로 구분되어 주어진다. $(1\le N\le 200\, 000;$ $0\le M\le 300\, 000)$
둘째 줄부터 $M$개의 줄에 걸쳐 두 정수 $v$, $w$가 공백으로 구분되어 주어진다. 이는 $v$번 정점을 시작점으로 하고, $w$번 정점을 끝점으로 하는 방향 간선을 의미한다. $(1\le v,w\le N)$
출력
첫째 줄에 히바이가 최소 몇 개의 색깔을 사용해야 하는지 출력한다.
예제 입력 1
3 3 1 2 1 3 2 3
예제 출력 1
3
예제 입력 2
4 0
예제 출력 2
1
출처
- 문제를 만든 사람: hibye1217
- 문제를 검수한 사람: iktk, minjunnick, mujigae, pyb1031, utilforever
© 2026 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호