5261 : A62 - 깊이 우선 탐색
•시간제한: 2.000 S
•메모리제한: 1024 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
각 정점에 $1, 2, \dots, N$ 의 번호가 붙은 $N$ 개의 정점과 $M$ 개의 간선으로 이루어진 무향 그래프가 주어집니다. $i$ 번째 간선은 정점 $A_i$ 와 정점 $B_i$ 를 연결합니다.
이 그래프 전체가 연결되어 있는지 판정하여 다음과 같이 출력하세요.
[제약 조건]
• $2 \le N \le 10^5$
• $1 \le M \le \min(10^5, \frac{N(N-1)}{2})$
• $1 \le U_i, V_i \le N$
• 입력되는 모든 값은 정수입니다.
이 그래프 전체가 연결되어 있는지 판정하여 다음과 같이 출력하세요.
- 그래프가 연결되어 있다면,
The graph is connected.라고 출력한다. - 그렇지 않다면,
The graph is not connected.라고 출력한다.
[제약 조건]
• $2 \le N \le 10^5$
• $1 \le M \le \min(10^5, \frac{N(N-1)}{2})$
• $1 \le U_i, V_i \le N$
• 입력되는 모든 값은 정수입니다.
입력 설명
첫째 줄에 $N, M$ 이 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보가 주어집니다.
둘째 줄부터 $M$ 개의 줄에 걸쳐 간선 정보가 주어집니다.
출력 설명
문제의 요구사항에 따라 연결 여부를 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 2
1 3
2 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
The graph is connected.