글 읽기 - 틀린 부분을 찾기가 어렵네요

kth990303 3년 전 0

트리의 개수를 구하는 문제이므로,

트리를 vector에 담아 dfs로 접근하였습니다.

접근 방법은 제 생각엔 틀리지 않은 것 같은데, WA를 받은 이유가 뭔질 모르겠네요.

25%에서 틀립니다..

도움 부탁드립니다 ㅠㅠ 감사합니다.

#include <iostream>
#include <vector>
using namespace std;
int N, M, cnt;
const int MAX = 501;
vector<int> v[MAX];
bool visit[MAX];
// 트리이면 tr(tree)=true, 아니면 tr=false를 리턴함
bool dfs(int cur, bool flag) {
	// 트리인지 아닌지 여부: tr
	bool tr = flag;
	for (auto i : v[cur]) {
        // 방문한 노드이면 (싸이클 방지)
		if (visit[i]) {
			tr = false;
			break;
		}
        // 방문하지 않은 노드이면
		if (!visit[i]) {
			visit[i] = true;
			// 한번 false면 계속 false로 가도록 tr를 인자로
			tr = dfs(i, tr);
		}
	}
	return tr;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	int tc = 1;
	while (cin >> N >> M) {
        // test case가 여러 개이므로 초기화 작업을 해줍니다
		if (!N && !M)
			break;
		for (auto& i : v)
			i.clear();
		fill(visit, visit + MAX, false);
		cnt = 0;
        // 트리를 구현합니다.
		for (int i = 0; i < M; i++) {
			int a, b;
			cin >> a >> b;
			v[a].push_back(b);
		}
        // 트리를 순회합니다.
        // 트리가 맞을 경우 cnt를 증가시킵니다.
		for (int i = 1; i <= N; i++) {
			if (!visit[i]) {
				if (dfs(i))
					cnt++;
			}
		}
        // 답을 출력합니다.
		if (!cnt)
			cout << "Case " << tc << ": No trees.\n";
		else if (cnt == 1)
			cout << "Case " << tc << ": There is one tree.\n";
		else
			cout << "Case " << tc << ": A forest of " << cnt << " trees.\n";
        // 테스트 케이스가 끝났으므로 case %d 부분의 %d를 증가시킵니다.
		tc++;
	}
}

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

문제

문제

출처

ICPC

틀린 부분을 찾기가 어렵네요

kth990303 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말