글 읽기 - 반례를 못찾겠습니다

xorms86 3년 전 0

그림도 그려가면서 반례를 찾으려 했지만 못찾았습니다.

도와주세요

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

int com[101][101];
bool visit[101];
queue <int> q;

int main() {

	int n;
	int pair;

	cin >> n >> pair;

	int x, y;
	cin >> x >> y;
	com[x][y] = 1;
	com[y][x] = 1;
	q.push(x);
	q.push(y);

	for (int i = 2; i <= pair; i++) {
		cin >> x >> y;

		com[x][y] = 1;
		com[y][x] = 1;
	}

	int count = 0;
	while (!q.empty()) {
		int front = q.front();

		if (!visit[front]) {
			for (int i = 1; i <= n; i++) {
				if (com[front][i] == 1) {
					q.push(i);
				}
			}
			visit[front] = true;
			count++;
		}
		q.pop();
	}
	if (visit[1])
		cout << count - 1;
	else
		cout << 0;

	
}

xorms86 3년 전 0

@auddl0756

그래프배열을 채우고 나서 처음입력, 즉 예제입력 기준으로 노드 1이랑 노드2로 부터 탐색하기 위해 큐에 넣어준것입니다

두 노드로 부터 탐색을 끝낸뒤 코드 마지막에 노드1이 방문되었으면 노드1의 수를 제외한 count-1를 출력하고 아니라면 0을 출력하도록 짜본건데 혹시 오류가 있을까요?

xorms86 3년 전 0

처음 입력노드가 1번노드가 아니여도, 다른노드가 1번노드랑 이어져만 있다면 결국엔 큐에 들어오게 되게끔 짜서 방문이 되긴 하는데 안되는 반례가 있을까요?

xorms86 3년 전 0

아니였네요..

5
3
4 5
1 2
2 3

정답은 2지만

말씀대로 0이 나와버리네요.. 다시 고민해보겠습니다!

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