moner_ari   8달 전

"정점 N개, 간선 M개로 구성된 무방향 그래프 G가 입력으로 주어진다. G에 존재하는 서로 다른 두 사이클(cycle)을 c1, c2라 하자. 이때 임의의 두 사이클 c1, c2에 대해 이들이 공유하는 정점이 최대 1개인 그래프라면 존재하는 서로 다른 사이클의 개수를 출력하고, 그렇지 않다면 'NIE'를 출력하시오."

제한: 1 <= N, M <= 106 / 입력으로 주어지는 모든 그래프에서, 임의의 두 정점을 잇는 간선은 최대 1개이다.

입력 양식: 입력은 여러 개의 테스트 케이스로 구성되어 있다. 테스트 케이스의 개수가 첫 줄에 주어진 다음, 2번째 줄부터는 각각의 테스트 케이스 입력이 주어진다. 각 테스트 케이스마다, 첫 줄에는 자연수 N, M이 주어진다. 다음 M개 줄에는 그래프 G를 구성하는 간선이 연결하는 서로 다른 두 정점 u, v(0 <= u, v < N)가 입력으로 주어진다.

유의 사항: 옛날 문제 특성상 테스트 케이스의 개수를 알려주지 않았으나, 의도한 시간 복잡도에 맞게 설정되어 있습니다.

댓글을 작성하려면 로그인해야 합니다.