[백준 2617] 구슬 찾기

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

2617번: 구슬 찾기

요구사항

1. 중간 값이 될 수 없는 수의 개수 찾기

 

풀이

 중간 값이 될 수 없다 == 현재 구슬보다 무겁거나or가벼운것이 (n+1)/2 보다 많을때

dfs로 현재 구슬보다 무거운 구슬이 몇개 인지 구한다

44

#include <iostream>
#include <queue>
#include <vector>
#include <string.h>

using namespace std;
#define Input(n,m) scanf("%d%d",&n,&m);
#define For(i ,x, n) for(int i=x ; i < n ; i++)

int n, m;
vector<int> vmax[100];
vector<int> vmin[100];
int visit[100];
int maxnum[100];
int minnum[100];

void maxdfs(int now,int start) {
	visit[now] = 1;
	maxnum[start]++;
	for (int i = 0; i < vmax[now].size(); i++) {
		int next = vmax[now].at(i);
		if (visit[next] == 0)
			maxdfs(next,start);
	}
}

void mindfs(int now, int start) {
	visit[now] = 1;
	minnum[start]++;
	for (int i = 0; i < vmin[now].size(); i++) {
		int next = vmin[now].at(i);
		if (visit[next] == 0)
			mindfs(next, start);
	}
}

int main(){
	Input(n, m);
	For( i, 0, m){
		int x, y;
		Input(x, y);
		vmax[x].push_back(y);
		vmin[y].push_back(x);
	}
	For(i,1,n+1) {
		memset(visit, 0, sizeof(visit));
		maxdfs(i,i);
	}
	For(i, 1, n + 1) {
		memset(visit, 0, sizeof(visit));
		mindfs(i, i);
	}
	int criteria = (n+1) / 2;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		if (maxnum[i] > criteria)
			ans++;
		if (minnum[i] > criteria)
			ans++;
	}
	cout << ans << endl;

}