[BOJ 26146] 즉흥 여행 (Easy)

View as PDF

Submit solution

Points: 4
Time limit: 2.0s
Memory limit: 1G

Problem types
Allowed languages
Assembly, Awk, C, C++, Java, Pascal, Perl, Python, Sed, Text

철민이는 종강을 기념하여 $ N $개의 나라로 즉흥 여행을 떠나기로 했다.</p>

철민이의 조사에 따르면, $ N $개의 나라 사이에는 총 $ M $개의 항공편이 있으며, 각각의 항공편은 출발하는 나라와 도착하는 나라가 정해져있다.

철민이는 즉흥 여행인 만큼 여행 계획을 짜는 대신, 아래 방식으로 여행하겠다는 계획만 세웠다.

  • 우선 여행을 시작할 나라를 정한 뒤, 그 나라로 간다.
  • 그 뒤로, 현재 있는 나라에서 출발하는 항공편 중 원하는 걸 골라서 탄다.
  • 철민이는 하나의 나라를 여러 번 방문할 수 있으며, 하나의 항공편을 여러 번 사용할 수 있다.

위 계획을 본 당신은 철민이가 $ N $개의 나라를 모두 여행할 수 있을지 걱정이 되기 시작했고, 철민이가 선택하는 시작점과 관계없이 모든 나라를 여행할 수 있을지 미리 확인해보기로 했다.

입력 형식

첫째 줄에 나라의 개수 $ N $과 항공편의 개수 $ M $이 주어진다. $( 1 \le N \le 200\,000; $ $ 0 \le M \le 500\,000 )$</p>

둘째 줄부터 $ M $개의 줄에 걸쳐 항공편의 정보가 두 정수 $ v $ $ w $로 주어진다. 이는 $ v $번 나라에서 출발해 $ w $번 나라로 가는 항공편을 의미한다. $( 1 \le v, w \le N; $ $ v \neq w )$

출력 형식

시작점을 어떻게 골라도 모든 나라를 방문할 수 있는 경로가 있다면 Yes를, 아니면 No를 출력한다.

예제 입력 1

4 5
1 2
2 3
3 1
1 4
4 1

예제 출력 1

Yes

예제 입력 2

4 4
1 2
2 3
3 4
4 2

예제 출력 2

No

예제 입력 3

4 4
1 2
2 1
3 4
4 3

예제 출력 3

No

Comments

There are no comments at the moment.