글 읽기 - [4803/트리] 채점 12%에서 틀렸다고 뜹니다..

ychooni 7년 전 0

(간선 수 = 정점 수 - 1) 을 만족하면 트리라고 해서 문제를 풀었는데요,

제가 뭘 간과하고 있는 걸까요? ㅜㅜ

#include <stdio.h>

int N, M, edge, vertex, tc;
int g[501][501], check[501];

void dfs(int s)
{
	vertex++;
	check[s] = 1;

	for(int i=1; i<=N; i++)
		if(g[s][i]) {
			edge++;
			if(!check[i])
				dfs(i);
		}
}

int main()
{
	while(1) {
		int i, j, a, b, ans=0;
		scanf("%d %d", &N, &M);
		if(!N && !M) return 0;

		for(i=0; i<M; i++) {
			scanf("%d %d", &a, &b);
			g[a][b] = g[b][a] = 1;
		}

		for(i=0; i<=N; i++) 
			check[i] = 0;
		
		for(i=1; i<=N; i++) {
			if(!check[i]) {
				vertex = edge = 0;
				dfs(i);
				if((edge>>1) == vertex-1)
					ans++;
			}
		}
			
		printf("Case %d: ", ++tc);
		if(ans == 1) puts("There is one tree.");
		else if(ans > 1) printf("A forest of %d trees.\n", ans);
		else puts("No trees.");
	}
    return 0;
}

yclock 7년 전 3

이 문제를 풀지 않았습니다. 소스를 자세히 읽지 않았습니다.

입력으로 주어지는 간선 (a, b)에서 a != b가 보장되지 않습니다.

(edge>>1) 부분에서 자기 자신이 사이클을 이루는 경우, 값이 내림으로 계산되어서 트리로 판단할 수 있을 것 같습니다.

edge == (vertex-1)<<1로 고쳐야 할 것 같습니다.

yclock 7년 전 1

길이가 1인 사이클을 고려하여 맞았습니다.

ychooni 7년 전 1

@yclock

답변 감사합니다.

말씀하신것 처럼 a!=b라는 보장이 없고,

a==b 인 경우

(edge>>1) == vertex-1) 보다는 edge == (vertex-1)<<1 의 표현이 맞는 것 같습니다.

그런데, 위의 경우 또 제가 잘못한 것이,

테케가 여러개인데, 그래프 g를 초기화를 안해주어서 틀린게 일단 주된 문제였던 것 같구요.

음, 데이터가 약하다고 표현해야하나? .

그래프 초기화만 추가하고 (edge>>1) == vertex-1) 코드를 그대로 사용했음에도 AC를 받았네요..

ps. 답변 뿐만아니라 님의 소스코드를 통해 많은 것 배워갑니다.(테케를 카운트 하는 변수를 이용해서 굳이 멤셋을 할 필요가 없다는 테크닉..ㅎ) 답변 감사합니다..!!

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

문제

문제

출처

ICPC

[4803/트리] 채점 12%에서 틀렸다고 뜹니다..

ychooni 7년 전 0

yclock 7년 전 3

yclock 7년 전 1

ychooni 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말