글 읽기 - [공지사항 확인 완료] 반례를 찾아주세요.

doryeongpark 5년 전 0

맵으로 구성된 인접리스트, 큐를 활용하여 BFS로 돌렸습니다.

양방향 그래프로 간주하고 풀었구요. 정점의 개수가 1인 경우 1을 출력하도록 분기처리하였습니다.

질문을 많이 참고해보려 했지만

반례를 도무지 못찾겠습니다. ㅠ

도와주시면 감사드리겠습니다!

#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<string>
#include<set>

std::map<int, std::vector<int>*> adjList;

int edgeCnt;
int vtxCnt;

std::vector<int> visited; 
std::queue<int> queue;

std::set<int> looper;

int isolated = 0;//고립된 연결요소의 개수

auto contains(std::vector<int> v, int integer)
-> bool
{
	int size = v.size();
	for(int i = 0; i < size; ++i){ if(v.at(i) == integer){ return true; } }
	return false;
}

void bfs(){
	if(queue.empty()){++isolated; return;}
	auto qSize = queue.size();
	for(int i = 0; i < qSize; ++i){
		int val = queue.front();
		auto toList = adjList[val];
		int tlSize = toList->size();
		for(int j = 0; j < tlSize; ++j){
			auto to = toList->at(j);
			if(contains(visited, to)){continue;}
			visited.emplace_back(to);
			queue.push(to);
		}
		queue.pop();
	}
	bfs();
}

int main(){
	
	std::cin >> vtxCnt;
	std::cin >> edgeCnt;

	if(vtxCnt == 1){ std::cout << "1" << std::endl; return 0; }

	for(int i = 0; i < edgeCnt; ++i){
		int from = 0;
		int to = 0;
		std::cin >> from;
		std::cin >> to;

		//Key가 존재하지 않을 경우(from -> to)
		if(adjList.end() == adjList.find(from)){
			std::vector<int>* v = new std::vector<int>;
			adjList.insert(std::make_pair(from, v));
		}
		adjList.at(from)->emplace_back(to);
		//Key가 존재하지 않을 경우(to -> from)
		if(adjList.end() == adjList.find(to)){
			std::vector<int>* v = new std::vector<int>;
			adjList.insert(std::make_pair(to, v));
		}
		adjList.at(to)->emplace_back(from);
		
		looper.insert(to);
		looper.insert(from);
		
	}

	for(auto it = looper.begin(); it != looper.end(); ++it){
			auto val = *it;
			if(contains(visited, val)){continue;}
			queue.push(val);
			visited.emplace_back(val);
			bfs();
	}

	std::cout << isolated << std::endl;
	
	/*int pause;
	std::cin >> pause;*/
}

dyk777 5년 전 3

반례 드립니다.

https://ideone.com/JFGUvg

Input:
3 1
1 2

Correct answer:
2

Test output:
1

doryeongpark 5년 전 0

감사합니다!

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

문제

문제

출처

ICPC

[공지사항 확인 완료] 반례를 찾아주세요.

doryeongpark 5년 전 0

dyk777 5년 전 3

doryeongpark 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말