[백준 2617: 구슬 찾기] - C++

www.acmicpc.net/problem/2617

2617번: 구슬 찾기

#include <iostream>
#include <vector>
#include <string.h>
using namespace std;

bool visited[100];
vector<int> heavyMap[100];
vector<int> lightMap[100];
int check[100];
int cnt = 0;

void D(vector<int> _map[100], int n)
{
	int size = _map[n].size();
	for (int i = 0; i < size; i++)
	{
		if (!visited[_map[n][i]])
		{
			visited[_map[n][i]] = true;
			cnt++;
			D(_map,_map[n][i]);
		}
	}

}
int main() {
	int n, m;

	cin >> n >> m;

	int input1;
	int input2;
	for (int i = 0; i < m; i++)
	{
		cin >> input1 >> input2;

		heavyMap[input2].push_back(input1);
		lightMap[input1].push_back(input2);
	}

	int result = 0;

	for (int i = 1; i <= n; i++)
	{
		memset(visited, false, sizeof(visited));
	
		cnt = 0;
		D(heavyMap,i); //해당 번호보다 무거운 구슬 갯수 세기
		if (cnt >= (n + 1) / 2) //평균이상 갯수라면 
		{
			result++;
		}

		cnt = 0;
		D(lightMap, i);//해당 번호보다 가벼운 구슬 갯수 세기
		if (cnt >= (n + 1) / 2) //평균이상 갯수라면 
		{
			result++;
		}
	}
	
	cout << result << endl;
	return 0;
}