글 읽기 - 어느부분에서 실수를 했는지 잘모르겠습니다....

s7d8f9 6년 전 0

간단한 트리 문제인데 어느부분에서실수를 하였는지 잘 모르겠습니다...ㅠ

대부분의 테스트 케이스를 테스트 해보았는데 정상적으로 작동하는데 .... 문제를 여러번 읽어봐도 잘못된 부분을 찾지 못하겠습니다.

벡터를 이용하여 각 노드의 다음노드를 저장하고 이동하면서 map을 통해 그 노드의 방문횟수를 저장하고 그 횟수를 바탕으로 순환 , 비순환 여부를 확인하는 방식으로 구현하였습니다.

코드가 다소 깔끔하지는 못하지만 ㅠㅠ. ..도와주시면 감사하겠습니다...

#include <iostream>
#include <vector>
using namespace std;

int n, m, nd1, nd2, cur, tr, map[505], t = 1,error;
vector<int> v[505];

void fun(int nd)
{
	if (v[nd].size() == 0)
		return;
	else
	{
		for (int i = 0; i < v[nd].size(); i++)
		{
			if (map[v[nd][i]] > 0)
			{
				error = 1;
				break;
			}
			map[v[nd][i]]++;
			fun(v[nd][i]);
		}
	}
}

int main()
{
	while (1)
	{
		scanf("%d%d", &n, &m);
		if (n == 0 && m == 0)
			break;

		tr = 0;
		for (int i = 1; i <= n; i++)
			v[i].clear();
		fill_n(&map[0], 505, 0);

		for (int i = 0; i < m; i++)
		{
			scanf("%d%d", &nd1, &nd2);
			v[nd1].push_back(nd2);
		}
		for (int i = 1; i <= n; i++)
		{
			error = 0;
			fun(i);
			if (map[i] == 0 && error == 0)
				tr++;
		}
		if (tr == 0)
			printf("Case %d: No trees.\n", t, tr);
		else if (tr == 1)
			printf("Case %d: There is one tree.\n", t);
		else
			printf("Case %d: A forest of %d trees.\n", t, tr);
		t++;
	}
	return 0;
}

skynet 6년 전 0

저도 아직 AC가 나오지 않았지만.

nd1이 nd2의 루트노드라는 보장이 없는거 같습니다.

그리고 밑에 질문 검색을 보니

nd1 = nd2인 경우도 있는거 같군요

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

문제

문제

출처

ICPC

어느부분에서 실수를 했는지 잘모르겠습니다....

s7d8f9 6년 전 0

skynet 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말