Blackouts and Dark Nights (또는 ACM++)는 전력을 공급하는 회사다. ACM++는 여러 발전소를 소유하고 있는데, 각 발전소는 바로 인접한 지역에 소규모로 전력을 공급한다. 이러한 조직 구조는 많은 문제점을 가져오고 있다. 한 지역에는 전력이 심하게 부족하지만 나머지 모든 지역에서는 전력 공급이 매우 여유로운 상황은 꽤 자주 일어나고 있다.
이에 따라 ACM++는 몇몇 발전소를 잇는 전력 공급망을 연결하기로 결정했다. 적어도 첫 단계에서는 모든 발전소를 하나의 공급망으로 연결할 필요는 없지만, 반대로 몇몇 중요한 곳에 불필요한 연결로 인해 예산을 낭비할 수도 있다. (즉, 전력 공급망이 불필요한 사이클을 가지게 될 수도 있다.) 공급망을 구축하기 위한 다양한 계획이 만들어졌으며, 이들 계획의 복잡한 검토 절차가 시작되었다.
(실제로 반영되어야 하는) 계획을 검토하는 기준 중 하나는 구축된 공급망의 신뢰도이다. 이를 평가하기 위해, 발생할 수 있는 최악의 상황으로 '발전소 중 하나에 문제가 생긴 결과, 구축한 전력 공급망이 여러 개로 분할되는 상황'을 가정하기로 했다. 물론 전력 공급망이 여러 개로 분리되어도 여전히 각각의 분리된 공급망은 정상적으로 작동하겠지만, 결국 각 공급망은 다시 동일한 문제점에 직면할 수 있는 만큼, 발전소 중 하나가 사라진다고 하더라도 분리된 공급망의 개수를 최소로 줄여야 한다.
여러분은 이러한 위험을 평가할 수 있는 프로그램을 작성해야 한다. 전력 공급망이 입력으로 주어졌을 때, (제거된 발전소는 제외하고) 발전소 하나를 제거했을 때 연결되지 않은 공급망의 개수의 최댓값을 구하는 프로그램을 작성하시오.
--------
[입력]
입력으로 여러 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 두 정수 1 <= P <= 10,000와 C >= 0이 입력으로 주어진다. P는 발전소의 개수로, 각 발전소는 0번부터 (P-1)번까지 순서대로 번호가 붙어 있다. C는 두 발전소를 연결하는 전선의 개수이다.
다음 C개 줄에는 전선으로 연결된 두 발전소의 번호 p1, p2가 입력으로 주어진다. 이때 p1, p2는 0 <= p1, p2 < P를 충족하는 두 정수로, 띄어쓰기로 구분되어 한 줄씩 주어진다. 이때 모든 전선은 정확히 1번씩만 주어지며, 임의의 두 발전소를 잇는 전선의 개수는 최대 1개만 존재한다.
입력의 마지막에는 2개의 0만이 주어진다.
--------
[출력]
각 테스트 케이스마다, 입력으로 주어진 공급망에서 하나의 발전소를 제거했을 때 연결되지 않은(즉, 분리된) 공급망의 개수의 최댓값을 한 줄에 하나씩 출력한다.
moner_ari 8달 전 1
[문제]
Blackouts and Dark Nights (또는 ACM++)는 전력을 공급하는 회사다. ACM++는 여러 발전소를 소유하고 있는데, 각 발전소는 바로 인접한 지역에 소규모로 전력을 공급한다. 이러한 조직 구조는 많은 문제점을 가져오고 있다. 한 지역에는 전력이 심하게 부족하지만 나머지 모든 지역에서는 전력 공급이 매우 여유로운 상황은 꽤 자주 일어나고 있다.
이에 따라 ACM++는 몇몇 발전소를 잇는 전력 공급망을 연결하기로 결정했다. 적어도 첫 단계에서는 모든 발전소를 하나의 공급망으로 연결할 필요는 없지만, 반대로 몇몇 중요한 곳에 불필요한 연결로 인해 예산을 낭비할 수도 있다. (즉, 전력 공급망이 불필요한 사이클을 가지게 될 수도 있다.) 공급망을 구축하기 위한 다양한 계획이 만들어졌으며, 이들 계획의 복잡한 검토 절차가 시작되었다.
(실제로 반영되어야 하는) 계획을 검토하는 기준 중 하나는 구축된 공급망의 신뢰도이다. 이를 평가하기 위해, 발생할 수 있는 최악의 상황으로 '발전소 중 하나에 문제가 생긴 결과, 구축한 전력 공급망이 여러 개로 분할되는 상황'을 가정하기로 했다. 물론 전력 공급망이 여러 개로 분리되어도 여전히 각각의 분리된 공급망은 정상적으로 작동하겠지만, 결국 각 공급망은 다시 동일한 문제점에 직면할 수 있는 만큼, 발전소 중 하나가 사라진다고 하더라도 분리된 공급망의 개수를 최소로 줄여야 한다.
여러분은 이러한 위험을 평가할 수 있는 프로그램을 작성해야 한다. 전력 공급망이 입력으로 주어졌을 때, (제거된 발전소는 제외하고) 발전소 하나를 제거했을 때 연결되지 않은 공급망의 개수의 최댓값을 구하는 프로그램을 작성하시오.
--------
[입력]
입력으로 여러 개의 테스트 케이스가 주어진다.
각 테스트 케이스의 첫 줄에는 두 정수 1 <= P <= 10,000와 C >= 0이 입력으로 주어진다. P는 발전소의 개수로, 각 발전소는 0번부터 (P-1)번까지 순서대로 번호가 붙어 있다. C는 두 발전소를 연결하는 전선의 개수이다.
다음 C개 줄에는 전선으로 연결된 두 발전소의 번호 p1, p2가 입력으로 주어진다. 이때 p1, p2는 0 <= p1, p2 < P를 충족하는 두 정수로, 띄어쓰기로 구분되어 한 줄씩 주어진다. 이때 모든 전선은 정확히 1번씩만 주어지며, 임의의 두 발전소를 잇는 전선의 개수는 최대 1개만 존재한다.
입력의 마지막에는 2개의 0만이 주어진다.
--------
[출력]
각 테스트 케이스마다, 입력으로 주어진 공급망에서 하나의 발전소를 제거했을 때 연결되지 않은(즉, 분리된) 공급망의 개수의 최댓값을 한 줄에 하나씩 출력한다.