연결 여부 판정

시간 제한1초메모리 제한128 MB

요약
n개의 지점과 k개의 연결이 주어질 때 모든 지점이 서로 도달 가능한지 판정한다.
난이도

쉬움10점 중 3점

유형
그래프, DFS, 유니온 파인드
정답자
아직 제출이 없습니다

문제

어떤 세계에 nn개의 사이트가 있고, 이들은 여러 개의 (가상) 통로로 서로 연결되어 있습니다. 각 통로는 두 사이트를 잇는 양방향 연결입니다. 즉, 사이트 aa와 사이트 bb 사이에 연결이 있으면 aa에서 bb로도, bb에서 aa로도 이동할 수 있습니다.

주어진 연결들만으로 모든 사이트에서 다른 모든 사이트로 이동할 수 있는지, 즉 그래프가 하나로 연결되어 있는지를 판정하세요.

입력

첫 번째 줄에 테스트 케이스의 개수 TT가 주어집니다 (T≤50T \le 50).

이어지는 각 줄에는 하나의 테스트 케이스가 주어집니다. 각 테스트 케이스의 첫 번째 수는 사이트의 개수 nn입니다 (n≤100n \le 100). 사이트에는 00부터 n−1n-1까지 번호가 매겨져 있습니다. 두 번째 수는 연결의 개수 kk입니다 (k≤200k \le 200). 그 뒤에는 kk개의 연결이 각각 두 정수의 쌍으로 주어집니다.

같은 연결이 여러 번 주어질 수 있고, 한 사이트에서 자기 자신으로 가는 연결(자기 연결)도 있을 수 있습니다.

출력

각 테스트 케이스마다 모든 사이트에서 다른 모든 사이트로 가는 경로가 존재하는지 확인하여, 존재하면 Connected.를, 존재하지 않으면 Not connected.를 한 줄에 출력하세요.

예제1

  1. 예제 1

    입력
    3
    5 4 0 1 1 2 2 3 3 4
    6 6 0 1 1 2 2 0 3 4 4 5 5 3
    5 9 0 1 1 2 2 3 3 4 1 0 2 1 3 2 2 3 4 3 
    
    예상 출력
    Connected.
    Not connected.
    Connected.