[백준/BOJ] 백준 7535번 : A Bug’s Life

https://www.acmicpc.net/problem/7535

7535번: A Bug’s Life

 

dfs(깊이 우선 탐색)을 수행하면서 노드를 1과 -1로 번갈아가면서 색을 칠하는데, 인접한 노드 간 같은 색으로 색칠되는 게 있는지 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

int t;
int n, m;
vector<int> adj[2005];
int color[2005]; //각 노드마다 색칠(1, -1)을 해서, 인접한 노드와 같은 색이 겹치지 않는지 확인한다
bool suspicious;

vector<string> result;

void pre() {
	for (int i = 0; i < 2005; i++) {
		adj[i].clear();
		color[i] = 0;
	}
	suspicious = false;
}

void dfs(int here, int here_color) {
	color[here] = here_color;

	for (int i = 0; i < adj[here].size(); i++) {
		int there = adj[here][i];

		if (color[there] == 0) { //there가 아직 색이 칠해지지 않았을때
			dfs(there, here_color*(-1));
		}

		if (color[here] == color[there]) { //인접한 노드와 같은 색이 될때
			suspicious = true;
		}
	}
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> t;

	for (int tc = 0; tc < t; tc++) {
		pre();
		cin >> n >> m;

		for (int i = 0; i < m; i++) {
			int u, v;
			cin >> u >> v;

			adj[u].push_back(v);
			adj[v].push_back(u);
		}

		for (int i = 1; i <= n; i++) {
			if (color[i] == 0) {
				dfs(i, 1);
			}
		}

		if (suspicious == true) {
			result.push_back("Suspicious bugs found!");
		}
		else {
			result.push_back("No suspicious bugs found!");
		}
	}

	for (int i = 0; i < result.size(); i++) {
		cout << "Scenario #" << i + 1 << ":" << "\n";
		cout << result[i] << "\n";
		cout << "\n";
	}

	return 0;
}