글 읽기 - 반례좀 부탁드립니다... 코드 주석 달았습니다.

ansdlsrb1121 1년 전 0

질문 게시판 모든 반례 다 넣어봤는데 해결이 안됩니다.

도와주세요ㅠㅠ

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;
vector<int> vec[20001];
int visited[20001] = {};

void makeClean();
bool check(int v);

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int k;
	cin >> k;

	while (k--) {
		int v, e;
		cin >> v >> e;
		for (int i = 0; i < e; i++) {
			int temp1, temp2;
			cin >> temp1 >> temp2;
			vec[temp1].push_back(temp2);
			vec[temp2].push_back(temp1);
		}

		if (check(v)) {
			cout << "YES\n";
		}
		else {
			cout << "NO\n";
		}
		//초기화
		makeClean();
	}

	


	return 0;
}
bool check(int v) {
	
	queue<int> que;
	que.push(v);
	visited[v] = 1;

	while (!que.empty()) {
		int x = que.front();
		que.pop();
		for (int i = 0; i < vec[x].size(); i++) {
			if (visited[vec[x][i]] == 0) {
				que.push(vec[x][i]);
				visited[vec[x][i]] = visited[x] * -1; //-1을 곱해서 1or-1를 넣어줌
			}
			//인접 노드와 값이 동일한지 확인
			for (int j = 0; j < vec[vec[x][i]].size(); j++) {
				if (visited[vec[x][i]] == visited[vec[vec[x][i]][j]])
					return false; //동일할경우 false 리턴 (NO 출력)
			}
		}
	}
	//모든 노드가 연결이 안되어있을 경우 해당 노드를 방문하는 코드
	for (int i = 1; i <= v; i++) {
		if (visited[i] == 0)
			check(i);
	}
	
	return true;
}

void makeClean() {
	for (int i = 0; i < 20001; i++) {
		for (int j = 0; j < vec[i].size(); j++) {
			vec[i][j] = 0;
		}
	}
}

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

문제

문제

출처

ICPC

반례좀 부탁드립니다... 코드 주석 달았습니다.

ansdlsrb1121 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말