글 읽기 - 이분탐색 반례질문

hyj5419 5년 전 0

질문에 나온 예제 다 맞게 나오는데 계속 바로 틀립니다가 뜹니다. ㅠㅠㅠ

왜그럴까요 ㅠㅠ

반례좀 찾아주시면 정말 감사합니다!

#include<iostream>
#include<stdio.h>
#include<utility>
#include<vector>
#include<algorithm>
#include<stack>
#include<string.h>
using namespace std;

vector<int> adj[20005];

char color[3] = { 'A','B' };

int visit[20005];
int comp[20005];
int cnt = 0;
int isokay = 0;

void dfs(int k) {
	comp[k] = 1;
	int j = cnt % 2;
	cnt++;
	visit[k] = color[j];
	for (int n = 0; n < adj[k].size(); n++) {
		int new_v = adj[k][n];
		if (visit[new_v] ==0) {
			dfs(new_v);
		}
		else {
			if (visit[new_v] == visit[k]) {
				isokay = -1;
				return;
			}
		}
		if (isokay == -1) {
			return;
		}
	}if (isokay == -1) {
		return;
	}
}


int main() {
	int k;
	cin >> k;
	while (k--) {
		int V, E;
		scanf("%d%d", &V, &E);
		for (int i = 0; i < E; i++) {
			int a, b;
			scanf("%d%d", &a, &b);
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		for (int i = 1; i <= V; i++) {
			if (comp[i] != 1) {
				dfs(i);
			}

		}
		if (isokay != 0) {
			printf("NO\n");
		}
		else {
			printf("YES\n");
		}
		int cnt = 0;
		isokay = 0;
		memset(visit, 0, sizeof(visit));
		memset(comp, 0, sizeof(comp));
		for (int i = 1; i <= V; i++) {
			adj[i].clear();
		}
	}
}

yclock 5년 전 0

그래프에서 DFS로 각 노드를 방문하는 순서의 기우성과 이분그래프는 관련이 없습니다.

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

문제

문제

출처

ICPC

이분탐색 반례질문

hyj5419 5년 전 0

yclock 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말