글 읽기 - BFS 이외의 방법

201 4년 전 0

안녕하세요?

edge를 작은 원소가 앞에 오도록 swap 해준 다음, 첫 번째 원소와 두 번째 원소를 기준으로 sorting을 하였습니다.

그 후 edge를 하나씩 확인하는 방식으로 풀었습니다.

질문 게시판에 있는 반례를 테스트해봐도 정답과 같은 결과가 나오는데, 혹시 반례나 잘못된 부분이 있다면 알려주실 수 있을까요?

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef struct{
	int f;	
	int s;
}Edge;

int vis[20100] = {0,}; 
Edge edge[200100] = {0,};

void swap(int& a, int& b){
	int temp = a;
	a = b;
	b = temp;
}

bool inc_(const Edge& a, const Edge& b){
	if(a.f != b.f)
		return a.f < b.f;
	else
		return a.s < b.s;
}

void sol(){
	bool ret = true;
	memset(vis,0,sizeof(vis));
	memset(edge,0,sizeof(edge));
	int v,e;
	cin >> v >> e;
	for(int i=0; i<e; i++){
		cin >> edge[i].f >> edge[i].s;
		if(edge[i].f > edge[i].s)
			swap(edge[i].f, edge[i].s);
	}
	sort(edge, edge + e, inc_);
	for(int i=0; i<e; i++){
		if(vis[edge[i].f] == 0 && vis[edge[i].s] == 0){ 
			vis[edge[i].f] = 1;
			vis[edge[i].s] = -1;
		}
		
		else if(vis[edge[i].f] != 0 && vis[edge[i].s] == 0){
			vis[edge[i].s] = -vis[edge[i].f];
		}
			
		else if(vis[edge[i].f] == 0 && vis[edge[i].s] != 0){
			vis[edge[i].f] = -vis[edge[i].s];
		}
			
		else{
			if(vis[edge[i].s] == vis[edge[i].f]){
				ret = false;
				break;
			}
		}
	}
	if(ret == true)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

int main(){
	int k;
	cin >> k;
	
	while(k>0){
		sol();
		k--;
	}
	return 0;
}

djm03178 4년 전 1

다음과 같은 경우가 반례입니다.

https://ideone.com/USZPGW

201 4년 전 0

감사합니다~

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

문제

문제

출처

ICPC

BFS 이외의 방법

201 4년 전 0

djm03178 4년 전 1

201 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말