글 읽기 - 반례 부탁드립니다

mintflavoredwater 1년 전 0

16%에서 자꾸 틀립니다.. ㅠㅠ 제 이전에 올라온 반례는 전부 테스트 해봤습니다

#include <iostream>
#include <vector>
#include <queue>

class Graph {
public:
	Graph(int n, int k) : NOV(n) {
		isconnected = std::vector<std::vector<bool>>(n, std::vector<bool>(n, false));
		ischecked = std::vector<bool>(n, false);

		for (int i = 0; i < k; ++i) {
			int src, dst;
			std::cin >> src >> dst;
			isconnected[src - 1][dst - 1] = true;
			isconnected[dst - 1][src - 1] = true;
		}
	}

	int solve() {
		int cnt = 0;

		for (int i = 0; i < NOV; ++i) {
			if (ischecked[i]) continue;
			bool istree = true;
			std::queue<std::pair<int, int>> queue;	// target, parent;
			queue.push({ i, -1 });

			while (!queue.empty()) {
				int target = queue.front().first;
				int parent = queue.front().second;
				queue.pop();

				if (ischecked[target]) istree = false;
				else {
					ischecked[target] = true;

					for (int i = 0; i < NOV; ++i)
						if (isconnected[target][i] && i != parent) queue.push({ i, target });
				}
			}

			if (istree) ++cnt;
		}

		return cnt;
	}

private:
	int NOV;
	std::vector<bool> ischecked;
	std::vector<std::vector<bool>> isconnected; // src -> dst
};

int main() {
	int n, k, cnt = 0;
	std::cin >> n >> k;

	while (n || k) {
		++cnt;
		int tmp = Graph(n, k).solve();
		
		if (tmp == 0) printf("Case %d: No trees.\n", cnt);
		else if (tmp < 2) printf("Case %d: There is one tree.\n", cnt);
		else std::cout << printf("Case %d: A forest of %d trees.\n", cnt, tmp);

		std::cin >> n >> k;
	}
}

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

문제

문제

출처

ICPC

반례 부탁드립니다

mintflavoredwater 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말