글 읽기 - bfs, set을 이용해서 짰는데 오답이 뜨는 이유를 모르겠어요

hwy16016 3년 전 0

bfs하면서 adj노드탐색할 때 번갈아가며 set a, b에 넣어주면서 중복확인을 했습니다.

어떤 문제일까요?

#include<cstdio>
#include<vector>
#include<queue>
#include<set>
using namespace std;
typedef vector<int> vi;
int isempty(vi& visited);
int put(set<int>& a, set<int>& b, int node, int f);

int main()
{
	int k, v, e;
	vi res;
	scanf("%d", &k);
	while(k--){
		scanf("%d %d", &v, &e);
		vector<vi> adj(v, vector<int>(0));
		set<int> a, b;
		int exitflag=0;
		for(int i=0;i<e;i++){
			int s, t;
			scanf("%d %d", &s, &t);
			adj[--s].push_back(--t);
			adj[t].push_back(s);
		}
		queue<int> q;
		vi visited(v, 0);
		while(isempty(visited)!=-1){
			int s=isempty(visited), f=1;
			q.push(s);
			a.insert(s);
			visited[s]=1;
			while(!q.empty()){
				int cur=q.front();
				f*=-1;
				for(int i=0;i<adj[cur].size();i++){
					int adjv=adj[cur][i];
					exitflag=put(a, b, adjv, f);
					if(visited[adjv]==0){
						q.push(adjv);
						visited[adjv]=1;
					}
					if(exitflag) break;
				}
				q.pop();
				if(exitflag) break;
			}
			if(exitflag) break;
		}
		if(exitflag) res.push_back(0);
		else res.push_back(1);
	}
	
	for(int i=0;i<res.size();i++){
		if(res[i]) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

int isempty(vi& visited){
	for(int i=0;i<visited.size();i++)
		if(visited[i]==0) return i;
	return -1;
}

int put(set<int>& a, set<int>& b, int node, int f){
	if(f==1) a.insert(node);
	else b.insert(node);
	if(a.find(node)!=a.end() && b.find(node)!=b.end()) return 1;
	else return 0;
}

hwy16016 3년 전 0

해결했습니다.

visited로 탐색했는지만 보면 bfs에서 탐색한 노드에 도착했을 때 이 노드가 a에 속했는지 b에 속했는지 알수가 없는데

f로 a/b 번갈아가며 계속 넣었기 때문에

길이가 홀수인 사이클이 그래프에 있게되면 a에 속한 노드의 인접노드들을 다시 a에 넣게 되어 틀린답이 나왔습니다.

visited배열의 내용을 0/1이 아닌 0/1/-1로 바꿔서 해결했습니다.

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

문제

문제

출처

ICPC

bfs, set을 이용해서 짰는데 오답이 뜨는 이유를 모르겠어요

hwy16016 3년 전 0

hwy16016 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말