[C++] 백준 1325번 효율적인 해킹

DFS, BFS 문제입니다.

어떤 컴퓨터에서 가장 많이 다른 컴퓨터를 해킹 할 수 있는지 찾는 문제입니다.
신뢰하는 컴퓨터를 해킹할 수 있으며, 해킹한 컴퓨터를 신뢰하는 컴퓨터도 해킹할 수 있습니다.

DFS를 통해서 신뢰하는 컴퓨터들을 찾을 수 있으며, 방문 배열을 만들어서 이미 방문한 곳을 가지 않습니다.

배열의 크기가 커서 vector를 사용했습니다.

 

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

vector<int> v[10010];
int visit[10010];
int arr[10010];
int c;

void DFS(int a, int x)
{
	visit[a] = 1;

	for (int i = 0; i < v[a].size(); ++i) {
		int b = v[a].at(i);
		if (visit[b] == 0) {
			DFS(b, x);
			++c;
		}
	}
}

int main(int argc, char *argv[])
{
	int n, m;
	int maxNum = -987654321;

	scanf("%d", &n);
	scanf("%d", &m);

	memset(visit, 0, sizeof(visit));

	for (int i = 1; i <= m; ++i) {
		int a;
		int b;

		scanf("%d", &b);
		scanf("%d", &a);

		v[a].push_back(b);
	}

	for (int i = 1; i <= n; ++i) {
		c = 0;
		memset(visit, 0, sizeof(visit));
		DFS(i, i);
		arr[i] = c;
		maxNum = max(maxNum, c);
	}

	for (int i = 1; i <= n; ++i) {
		if (arr[i] == maxNum) {
			printf("%d ", i);
		}
	}

	return 0;
}