글 읽기 - dfs로 풀었는데 틀린 이유를 모르겠습니다. (반례를 찾았으나 해결 못함)

imash0728 1년 전 0

5 4

1 2

1 3

2 4

3 5

YES

여러 반례를 찾았으나 해당 반례에서만 틀립니다.

아무리 코드를 봐도 이유를 모르겠어서 질문합니다.

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

vector<int> graph[20001];
int visit[20001] = { 0 };

bool dfs(int n, int c) {
	visit[n] = c; //1 or -1

	for (int i = 0; i < graph[n].size(); i++) {
		int next = graph[n][i];
		if (visit[next] == c ) { //같은색인데 인접함
			return false;
		}
		else if (visit[next] == 0 ) { //방문한적 없음
			return dfs(next, c * -1);
		}
	}

	return true;
}

int main() {
	cin.tie(0); cout.tie(0);
	ios::sync_with_stdio(false);

	int k;
	cin >> k;

	for (int i = 0; i < k; i++) {
		int v, e;
		bool isBip = true;
		cin >> v >> e;
		for (int j = 0; j < e; j++) {
			int a, b;
			cin >> a >> b;
			graph[a].push_back(b);
			graph[b].push_back(a);
		}

		for (int j = 1; j <= v; j++) { //비연결 그래프 고려
			if (visit[j] == 0 && isBip == true) {
				isBip = dfs(j, 1);
			}
		}
		
		if (isBip) {
			cout << "YES" << '\n';
		}
		else {
			cout << "NO" << '\n';
		}

		//배열 초기화
		for (int  j= 0; j < 20001; j++) {
			visit[j] = 0;
			graph[j].clear();
		}
	}

	return 0;
}

djm03178 1년 전 0

하나의 정점에서 시작하면 연결된 부분들을 전부 탐색해야 하는데, 17번째 줄에서 바로 return을 하고 있어 모든 연결된 간선을 다 보지 못하고 있습니다.

imash0728 1년 전 0

넵 감사합니다 확인하고 수정했습니다!

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

문제

문제

출처

ICPC

dfs로 풀었는데 틀린 이유를 모르겠습니다. (반례를 찾았으나 해결 못함)

imash0728 1년 전 0

djm03178 1년 전 0

imash0728 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말