글 읽기 - BFS 이분그래프 왜틀렸는지 모르겠어요 C++

pianosiwon 2년 전 0

연결되지 않은 그래프여도 작동하게 만들었어요

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

vector<int>v[20002];
queue<int>q;
int check[20002];

void removeall()
{
	for (int i = 1; i <= 20001; i++)
	{
		v[i].clear();
		check[i] = 0;
	}
	//for (int i = 0; i < q.size(); i++) q.pop();
}
int color = 1; // 1일때 파랑 2일때 빨강
void BFS1(int tmp)
{
	check[tmp] = 2;
	while (!q.empty())
	{
		int node = q.front();
		q.pop();
		bool flage = 0;
		for (int i = 0; i < v[node].size(); i++)
		{
			if (check[v[node][i]] == 0)
			{
				check[v[node][i]] = color;
				flage = 1;
				q.push(v[node][i]);
			}
		}
		if (flage == 1)
		{
			if (color == 1) color = 2;
			else color = 1;
		}
	}
}

bool BFS2(int V)
{
	for (int i = 1; i <= V; i++)
	{
		int color = check[i];
		for (int j = 0; j < v[i].size(); j++)
		{
			if (check[v[i][j]] == color) return 0;
		}
	}
	return 1;
}

int main()
{
	int T;
	cin >> T;
	for (int i = 0; i < T; i++)
	{
		removeall();
		int V, E;
		cin >> V >> E;
		int a, b;
		for (int j = 0; j < E; j++)
		{
			cin >> a >> b;
			v[a].push_back(b);
			v[b].push_back(a);
		}
		q.push(a);
		for (int j = 1; j <= V; j++)
		{
			if (check[j] == 0)
			{
				BFS1(j);
			}
		}
		//removeall();
		//cout << check[1] << check[2] << check[3] << check[4];
		if (BFS2(V)) cout << "YES\n";
		else cout << "NO\n";
	}
}

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

문제

문제

출처

ICPC

BFS 이분그래프 왜틀렸는지 모르겠어요 C++

pianosiwon 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말