[백준/BOJ] 백준 1325번 : 효율적인 해킹

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

1325번: 효율적인 해킹

here번 컴퓨터를 해킹하면 몇 개의 컴퓨터를 해킹할 수 있는지 구하는 함수를 만들었다.

 

코드

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

int n, m;
vector<int> adj[10001];
int visited[10001];

//here컴퓨터를 해킹하면 몇개의 컴퓨터를 해킹할 수 있는지 구한다
int Solve(int here)
{
	int ret = 1;

	visited[here] = 1;

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

		if (visited[there] == 0)
			ret += Solve(there);
	}

	return ret;
}

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

	int a, b;
	int max_hacking = -1;
	vector<int> max_hacking_number;
	int able_hacking;

	cin >> n >> m;

	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		adj[b].push_back(a); //그래프를 생성한다
	}

	for (int i = 1; i <= n; i++)
	{
		memset(visited, 0, sizeof(visited));

		able_hacking = Solve(i); //i번 컴퓨터를 해킹하면 몇개의 컴퓨터를 해킹할 수 있는지 구한다

		//지금까지 구한 개수보다 많을때
		if (max_hacking < able_hacking)
		{
			max_hacking = able_hacking;

			max_hacking_number.clear();
			max_hacking_number.push_back(i);
		}

		//지금까지 구한 개수와 같은 개수일때
		else if (max_hacking == able_hacking)
		{
			max_hacking_number.push_back(i);
		}
	}

	for (int i = 0; i < max_hacking_number.size(); i++)
		cout << max_hacking_number[i] << " ";

	return 0;
}