글 읽기 - 반례를 못찾겠습니다. 도와주세요 ㅠㅜ

alpa1072 7년 전 0

dfs를 이용해서 인접한 노드들의 색깔을 다르게 하고,

다시 check를 하는 방식인데

어디가 잘못된것일까요?

도와주세요 ㅠㅜ

#include<cstdio>
#include<vector>
#include<memory.h>
#include<queue>
#include<iostream>

using namespace std;

int T,v,e;
bool b;
bool ans;
int color[20002];
bool visited[20002];
bool set[20002];

//이분그래프인지 체크
void check(int here, vector<vector<int>>& graph) {
	queue<int> q;
	q.push(here);
	visited[here] = true;
	while(!q.empty()) {
		int cr = q.front();
		q.pop();
		for(int i=0;i<graph[cr].size();i++) {
			int temp = graph[cr][i];
			if(!visited[temp]) {
				visited[temp] = true;
				q.push(temp);
			}
			if(color[cr] == color[temp]) {
				ans = false;
				return ;
			}
		}
	}
}

//색칠하기
void dfs(int here, vector<vector<int>>& graph) {
	visited[here] = true;
	if(b) {
		color[here] = 1;
		b = false;
	}
	else {
		color[here] = -1;
		b = true;
	}
	for(int i=0;i<graph[here].size();i++) {
		int there = graph[here][i];
		if(!visited[there])
			dfs(there,graph);
	}
}

int main(void) {
	scanf("%d",&T);
	for(int t=0;t<T;t++) {
		ans = true;
		b = true;
		scanf("%d %d",&v,&e);
		vector<vector<int>> graph(v+1);
		for(int i=0;i<e;i++) {
			int a,b;
			scanf("%d %d",&a,&b);
			graph[a].push_back(b);
			graph[b].push_back(a);
		}
		int cnt=1;
		for(int i=1;i<graph.size();i++) {
			if(!visited[i]) {
				b = true;
				dfs(i,graph);
				set[cnt++] = i;
			}
		}
		memset(visited, false, sizeof(visited));
		for(int i=1;i<cnt;i++) {
			check(i,graph);
		}

		if(ans) printf("YES\n");
		else printf("NO\n");

		graph.clear();
		memset(visited,false,sizeof(visited));
		memset(color,0,sizeof(color));
	}
	return 0;
}

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

문제

문제

출처

ICPC

반례를 못찾겠습니다. 도와주세요 ㅠㅜ

alpa1072 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말