wikioi1501 두 갈래 나무의 최대 너비와 높이

1437 단어

제목 설명 Description


두 갈래 나무를 보여 최대 너비와 높이를 출력합니다.

입력 설명 Input Description


첫 번째 줄은 정수 n이다.
다음 n줄은 줄마다 두 개의 수가 있는데 i줄의 두 개의 수는 i의 노드가 연결된 두 개 정도의 아들의 번호를 대표한다.만약 어떤 아들이 비어 있지 않다면 0이다.

출력 설명 Output Description


출력은 모두 한 줄로 두 갈래 나무의 최대 너비와 높이를 출력하고 공백으로 구분합니다.

샘플 입력 샘플 입력



2 3
4 5
0 0
0 0
0 0

샘플 출력 샘플 출력


2 3

데이터 범위 및 힌트 Data Size & Hint


n<16
기본 첫 번째는 루트 노드입니다.
입력한 순서를 번호로 하다
2-N+1 줄은 이 노드의 왼쪽 아이와 오른쪽 아이를 가리킨다
#include <stdio.h>
#include <string.h>

int a[1000][2],s[1000];
int i,n,x,y; 

void dfs(int i,int k)
{
	s[k]=s[k]+1;
	if(k>x)	x=k;
	if(a[i][1]!=0)	dfs(a[i][1],k+1);
	if(a[i][2]!=0)	dfs(a[i][2],k+1);
}

int main()
{
	scanf("%d",&n);
	memset(a,0,sizeof(a));
	memset(s,0,sizeof(s));
	for(i=1;i<=n;i++)
		scanf("%d%d",&a[i][1],&a[i][2]);
	x=0;
	dfs(1,1);
	y=0;
	for(i=1;i<1000;i++)
		if(s[i]>y)	y=s[i];
	printf("%d %d",y,x);
	return 0;
}

좋은 웹페이지 즐겨찾기