글 읽기 - 바이러스 반례와 틀린 이유좀 찾아주시면 감사하겠습니다..

tkdrnjs67 3년 전 0

BFS로 풀어봤는데 그냥 바로 틀렸다고 뜨네요..

다른 분 코드와도 비교했을때, 별 다른 차이점은 못느껴 이렇게 질문 올립니다..

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

vector<vector<int>> network;
vector<bool> isVisited;
int numComputer, numLink;
int infectiedCom = 0;

void bfs(int start) {
	queue<int> q;
	q.push(start);
	isVisited[start] = true;
	while (!q.empty()) {
		int parentNode = q.front();
		q.pop();
		for (int i = 0; i < network[parentNode].size(); i++) {
			int childNode = network[parentNode][i];
			if (!isVisited[childNode]) {
				q.push(childNode);
				isVisited[childNode] = true;
				++infectiedCom;
			}
		}
	}
}

int main() {
	cin >> numComputer >> numLink;

	network.resize(numComputer + 1);
	isVisited.resize(numComputer + 1);

	for (int i = 0; i < numLink; i++) {
		int parent, child;
		cin >> parent >> child;
		network[parent].push_back(child);
	}

	fill(isVisited.begin(), isVisited.end(), false);

	bfs(1);

	cout << infectiedCom;

	return 0;
}

fbfbf1 3년 전 1

https://ideone.com/MOcy0D

양방향 그래프이기에

입력 받을 때

network[child].push_back(parent)를 추가해줘야됩니다.

38번째줄만 하게 되면 단방향 그래프이기에 틀렸습니다를 받게 됩니다.

추가만 해주면 맞았습니다 처리 됩니다.

tkdrnjs67 3년 전 0

아 양방향 그래프인걸 간과했네요.. 친절한 답변 감사합니다!

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

문제

문제

출처

ICPC

바이러스 반례와 틀린 이유좀 찾아주시면 감사하겠습니다..

tkdrnjs67 3년 전 0

fbfbf1 3년 전 1

tkdrnjs67 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말