글 읽기 - 이분그래프 문제

dldnjswo19 7년 전 2

이분 그래프의 정의가 자신과 연결된 다른 노드들은 자신의 영역이 아니면 되는데, 그럼 이 코드는 어떤 예외가 있는걸까요???

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

vector<int> a[20001];
int check[20001];
int flag = 1;

void dfs(int x) {
	
		check[x] = flag; // flag색으로 칠하면서 방문한 노드를 체크한다
	
	for (int i = 0; i < a[x].size(); i++) {
		int y = a[x][i];
		if (check[y] == 0) {
			flag = 3 - flag;// 방문 안한 노드로 갈때는 flag를 다른 색으로 바꿔주고 간다.
			dfs(y);
		}
	}
}

int main() {

	int times;
	cin >> times;

	while (times--) {
		int n, m;
		cin >> n >> m;
		flag = 1;

		for (int i = 0; i <= n; i++) {// 초기화 해준다
			a[i].clear();
			check[i] = 0;
		}

		for (int i = 0; i < m; i++) {// 입력받은 정보를 입력한다
			int u, v;
			cin >> u >> v;
			a[u].push_back(v);
			a[v].push_back(u);
		}

		dfs(1);// dfs를 하면서 방문 노드를 1 또는 2 로 체크한다. 0은 방문되지 않은 노드이다.

		bool result = true;

		for (int i = 1; i <= n; i++) {
			for (int k = 0; k < a[i].size(); k++) {
				if (check[a[i][k]] == check[i]) {//모든 노드를 돌면서, 자신과 연결된 노드가 자신과 같은 숫자면 false 이다
					
					result = false;
				}
				
			}
		}
		if (result)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	return 0;
}

yohan5050 7년 전 2

입력으로 주어지는 그래프의 정점들이 모두 연결되어 있지 않을 수도 있어요.

그러니까 주어지는 그래프가 여러 개의 덩어리로 이루어져 있을 수 있는거에요

올려주신 코드를 보면 dfs탐색을 1번 정점에서만 시작하시는 것 같은데,

예를 들어

4 2

1 2

3 4

이런 입력이 들어올 경우 1-2 만 dfs로 탐색하고 3-4는 탐색하지 않아서 Yes가 나오지 않고

No가 나와요.

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

문제

문제

출처

ICPC

이분그래프 문제

dldnjswo19 7년 전 2

yohan5050 7년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말