IOI 1996 day1 3- 학교 네트워크(Network of Schools) > 문제은행 : 정보올림피아드&알고리즘




2012 : 학교 네트워크(Network of Schools)

제한시간
1000 ms   
메모리제한
128 MB   
해결횟수
2 회   
시도횟수
4 회   

문제

여러 학교들이 컴퓨터 네트워크로 연결이 되어 있다. 

어떤 소프트웨어가 개발되어 한 학교로 왔을 때, 그 학교는 자기가 보내기로 되어 있는 다른 학교에게 

그 소프트웨어를 네트워크로 전달하도록 학교 사이에 합의가 되어 있다. 

이 과정을 되풀이하면 결국 모든 학교에 소프트웨어가 전달된다. A

학교에서 B 학교에 소프트웨어를 보내기로 되어 있는데 

B 학교도 A 학교로 소프트웨어를 또 보내도록 지정되는 것과 같은 경우는 없다.

 


이번 문제는 두 가지다. 우선 모든 학교에 새로 개발된 소프트웨어를 보내기 위해서 

처음에 그것을 보내야 하는 최소한의 학교 수를 계산하는 프로그램을 작성하는 것이다. 

또한 우리는 여러 학교 중 아무 한 곳에만 소프트웨어를 보내도 결국 모든 학교가 그 소프트웨어를 공급받게 하고 싶다. 

그러려면 소프트웨어 공급 네트워크 망을 최소 몇 군데 더 확장해야 하는지를 계산하는 것이 둘째 문제이다. 

여기서 한 군데 확장한다는 말은 어떤 학교에서 자기가 보내기로 배당된 학교에 보낼 대상 학교를 한 곳 더 추가한다는 뜻이다.


입력형식

입력파일의 첫 줄에는 네트워크 망에 든 학교의 개수를 나타내는 N(2≤N≤100)이 있다. 각 학교는 1부터 N까지의 수로 구분한다. 그리고 다음 N줄에는 1부터 N까지 각 학교가 소프트웨어를 보내기로 되어 있는 대상 학교의 번호가 들어있다. 각각의 목록은 0으로 끝난다. 소프트웨어를 보낼 학교가 하나도 없는 학교에 해당하는 줄에는 그냥 0만 있다.


출력형식

출력파일의 첫째 줄에는 첫째 문제의 정답이 자연수로 들어간다. 둘째 줄에는 둘째 문제의 정답을 적는다.


입력 예

5
2 4 3 0
4 5 0
0
0
1 0

출력 예

1
2


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP