산만한 고양이 > 문제은행

본문 바로가기


문제은행

3077 : 산만한 고양이

제한시간: 1Sec    메모리제한: 64mb
해결횟수: 0회    시도횟수: 0회    채점준비중입니다.



철민이는 고양이 한 마리를 키우고 있다. 철민이는 이 고양이를 위해 입체놀이터를 만들었는데 이 놀이터에는 N개의 방들과 M개의 복도들이 있다. 방들은 1번부터 N번까지 번호가 붙어 있고 한 복도는 두 개의 서로 다른 방을 연결하며 양방향으로 이동이 가능하다. 한 쌍의 방을 연결하는 복도는 최대 1개이다. 어떤 두 방도 하나 이상의 복도를 이용하여 서로 이동이 가능하다. 놀이터는 입체로 되어있어 복도가 교차하는 경우는 없다. 아래는 방이 4개, 복도가 5개가 있는 예제이다.

08b6f023ea4f0ddc33a2459594e06b23_1502449 

철민이네 고양이는 성격이 매우 산만해서 쉬지 않고 놀이터를 뛰어다닌다. 특히 k(≥3)개의 서로 다른 방 (a1, a2, ..., ak)의 순서를 정한 다음 그 순서대로 반복적으로 도는 경향이 있다. 즉, a1, a2, ..., ak, a1, a2, ..., ak, a1, a2, ... 의 순서를 말한다. 물론 그렇게 하려면 이 방들이 순서대로 복도로 연결되어 있어야 할 것이다. 즉, a1과 a2가 연결, a2와 a3이 연결,..., ak와 a1이 연결되어 있어야 한다.

 

철민이는 고양이가 너무 힘들까봐 반복적으로 도는 방법이 없도록 하고 싶다. 노력을 최소화하기 위해 단 한 개의 방만 제거해서 (그리고 그 방에 연결된 복도들은 폐쇄한다) 고양이가 반복적으로 도는 방법이 없도록 만들고 싶다.

 

앞의 예시처럼 방이 연결되어 있다면 방들 1, 2, 3의 순서로 반복적으로 돌 수가 있다. 또, 방들 1, 2, 4, 3의 순서로도 반복적으로 돌 수 있다. 여기서 2번방을 제거하면 반복적으로 돌 수 있는 방법이 없다. 3번방을 제거해도 같은 결과를 얻는다. 하지만 4번방의 경우에는 제거한다고 하더라도 여전히 반복적으로 돌 수 있는 방법이 있다.

 

방들의 연결 상태를 입력으로 받아서, 단 하나의 방을 제거하여 고양이가 반복적으로 도는 모든 방법을 없앨 수 있다면 그 방의 번호를 출력한다. 혹시 그러한 방이 여러 개가 있다면 그 방들의 번호의 합을 출력한다. 그러한 방이 없는 경우 0을 출력한다.
 


표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 방의 수를 나타내는 정수 N(2≤N≤300,000)과 복도의 수를 나타내는 정수 M(1≤M≤300,000)이 주어진다. 다음 M개의 각 줄에는 하나의 복도로 연결된 서로 다른 두 방의 번호가 주어진다. 입력으로 주어진 방들과 복도에서는 반복적으로 도는 방법이 적어도 하나는 있다는 것이 보장된다.


표준 출력으로, 단 하나의 방을 제거하여 고양이 가 반복적으로 도는 모든 방법을 없앨 수 있다면 그 방의 번호를 출력한다. 혹시 그러한 방이 여러 개가 있다면 그 방들의 번호의 합을 출력한 다. 그러한 방이 없는 경우 0을 출력한다.

부분문제의 제약 조건 
● 부분문제 1: 전체 점수 100점 중 12점에 해당하며 N≤5,000, M≤5,000 이다. 
● 부분문제 2: 전체 점수 100점 중 10점에 해당하며 M=N 이다.
● 부분문제 3: 전체 점수 100점 중 23점에 해당하며 1번 방과 2번 방, 2번 방과 3번 방, 3 번 방과 4번 방, ..., N번 방과 1번 방을 잇는 복도가 모두 존재한다.
● 부분문제 4: 전체 점수 100점 중 55점에 해당하며 원래의 제약조건 이외에 아무 제약조건이 없다.

[Copy]
4 5 
1 2 
2 3 
4 2 
4 3 
3 1
[Copy]
5


[Copy]
8 10 
5 4 
4 3 
3 5 
1 2 
1 5 
2 3 
5 6 
6 7 
7 4 
8 6
[Copy]
5


[Copy]
8 10 
1 2 
2 3 
3 4 
4 5 
5 6 
6 7 
7 8 
8 1 
2 7 
3 6
[Copy]
0



[도움말 보기]


HancomEducation E-mail : hancomc@hotmail.com, comkiwer@naver.com Tel : 070-7163-5782 FAX : 031-388-0996 정올소개 이용약관 개인정보처리방침
경기도 안양시 동안구 호계동 1065-10 협성골드프라자 601호, 경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호
Copyright@2010-2015 jungol. All right reserved.