글 읽기 - c++ 반례가 다맞는데 12퍼에서 틀리네요...

dhtmdgus2134 3년 전 0

코드가 엄청 지저분 해서 미리 죄송합니다...

오기로 끝까지 하다보니 이지경까지 됬네요...

bfs 함수로 먼저 색구분을 1,-1로 했구요

dfs 함수로 모든 경로를 돌면서 이전 경로와 같은 색이 있을 경우 false 리턴했습니다.

검사 도중 false 받으면 더이상 체크 안하도록 했습니다.

답은 sol 배열에 저장 했고 탐색이 모두 종료되고 테스트 케이스만큼 출력했습니다.

코드를 깨끗하게 수정할 수도 있으나 제가 무엇을 놓치고 있는지 정확하게 알기 위해서 그대로 올립니다

도움주실분께 미리 감사합니다.

#include<iostream>
#include<queue>
#include<vector>
#include<stack>
#include<cstring>
#define MAX 20001
using namespace std;

vector<int> v[MAX];
int check[MAX];
bool visited[MAX];
int t, n, c, a, b;

void makeTree(int a, int b) {
	v[a].push_back(b);
	v[b].push_back(a);
}
bool dfs(int a) {
	stack<int> s;
	s.push(a);
	while (!s.empty()) {
		int scnt = s.size();
		for (int i = 0; i < scnt; i++) {
			int x = s.top();
			s.pop();
			if (x > n) continue;
			if (visited[x]) continue;
			visited[x] = true;
			for (int j = 0; j < v[x].size(); j++) {
				int y = v[x][j];
				if (y > n) continue;;
				if (check[x] == check[y]) {
					return false;
				}
				s.push(y);
			}
		}
	}
	return true;
}
void bfs(int a) {
	int rvs = 1;
	queue<int>q;
	q.push(a);
	while (!q.empty()) {
		int cnt = q.size();
		for (int i = 0; i < cnt; i++) {
			int x = q.front();
			q.pop();
			if (check[x] != 0) continue;
			check[x] = rvs;
			for (int j = 0; j < v[x].size(); j++) {
				int y = v[x][j];
				if (y > n) continue;
				q.push(v[x][j]);
			}
		}
		rvs *= -1;
	}
}



int main(void) {
	cin >> t;
	int sol[5] = { 1, 1,1,1,1 };
	for (int i = 0; i < t; i++) {
		cin >> n >> c;
		for (int j = 0; j < c; j++) {
			cin >> a >> b;
			makeTree(a, b);
		}
		if (n == 1) {
			sol[i] = true;
			continue;
		}
		for (int j = 1; j <= n; j++) {
			bfs(j);
		}
		for (int j = 1; j <= n; j++) {
			if (!dfs(j)) {
				sol[i] = 0;
				break;
			}
		}
		v->clear();
		memset(visited, false, sizeof(visited));
		memset(check, 0, sizeof(check));
	}
	for (int i = 0; i < t; i++) {
		if (sol[i]) cout << "YES\n";
		else cout << "NO\n";
	}
}

dhtmdgus2134 3년 전 0

86번 라인

v->clear();

for(int j=0; j<=n;j++){

v[j].clear();

}

로 수정하니까 바로 통과되네요;

혹시 차이점 아시는 분 설명 부탁해요

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

문제

문제

출처

ICPC

c++ 반례가 다맞는데 12퍼에서 틀리네요...

dhtmdgus2134 3년 전 0

dhtmdgus2134 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말