백준 2458번: 키 순서

[문제 링크]

2458번: 키 순서

---

간단한 그래프탐색 문제였다.

자신의 키가 정확히 몇번째인지 알기 위해선 다른 모든 학생들과 그래프가 연결되어 있어야 한다.

우선, 연결되어 있는 학생들을 체크하는 함수는 dfs로 구현하였다.

학생 a보다 학생 b의 키가 더 큰지 여부를 확인하기 위해선 adj[a][b] == true 인지 확인하면 되고,

학생 a보다 학생 b의 키가 더 작은지 여부를 확인하기 위해선 그 반대인 adj[b][a] == true 인지 확인하면 된다.

따라서 키가 더 큰 학생들을 체크하는 dfs, 키가 더 작은 학생들을 체크하는 dfs를 수행하여 모든 학생들과 연결되어 있는지 알 수 있도록 구현하였다.

---

#include <iostream>
#include <cstring>
using namespace std;

int N, M;
bool adj[501][501];
bool visited[501];
const int DOWN = 1;
const int UP = 2;

int dfs(int here, int type) {
	int ret = 1;
	visited[here] = true;

	for (int i = 1; i <= N; i++) {
		if (type == DOWN) {
			if (adj[here][i] && !visited[i])
				ret += dfs(i, type);
		}
		else if (type == UP) {
			if (adj[i][here] && !visited[i])
				ret += dfs(i, type);
		}
	}

	return ret;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> N >> M;

	while (M--) {
		int a, b;
		cin >> a >> b;
		adj[a][b] = 1;
	}

	int result = 0;
	for (int i = 1; i <= N; i++) {
		memset(visited, false, sizeof(visited));
		int visitCnt = dfs(i, DOWN) + dfs(i, UP) - 1;
		if (visitCnt == N)
			result++;
	}

	cout << result << endl;

	return 0;
}