글 읽기 - 이분 그래프 질문

lwh1992 5년 전 0

안녕하세요. 이분 그래프를 풀면서 문제에 나온 예제와 질문들에 나온 반례들을 집어넣어 봐도 문제를 찾지 못해 질문을 올립니다.

부탁드려요ㅠㅠ

#include <iostream>
#include <stack>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;

int check[20001];
vector<int> line[20001];
bool flag = true;

void dfs(int node, int c) {
	check[node] = c;
	for (int i = 0; i < (int)line[node].size(); i++)
	{
		if (check[line[node][i]] == 0) {
			//printf(" ");
			dfs(line[node][i], 3-c);
		}
		else {
			if (check[line[node][i]] == 3 - c)//다른색
			{
				flag = true;
			}
			else {
				flag = false;
				break;
			}
		}
		
	}
}
int main() {
	
	int K, N, M;
	
	scanf("%d", &K);
	for (int j = 0; j < K; j++)
	{
		scanf("%d %d", &N, &M);
		for (int i = 0; i < M; i++) {
			int u, v;
			scanf("%d %d", &u, &v);
			line[u].push_back(v);
			line[v].push_back(u);
		}
		int che=0;
		while (line[che++].empty()){
			
		}

		dfs(--che, 1);
		if (flag == true)
			printf("YES\n");
		else
			printf("NO\n");

		memset(check, 0, sizeof(int)*(N+1));
		for (int i = 1; i <= N; i++)
		{
			line[i].clear();
		}
		flag =true;
	}
	
	getchar(); getchar();

}

luniro 5년 전 0

출력:
YES

정답:
NO

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

문제

문제

출처

ICPC

이분 그래프 질문

lwh1992 5년 전 0

luniro 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말