[백준1325]효율적인 해킹

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

입력

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다"를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이

메모리 제한 때문에 애먹었던 문제이다.
다엑스트라 느낌의 문제인데 일단 신뢰라는 관계 때문에
단방향으로 그래프를 받아준다.
신뢰도라는게
3,1로 입력을 받으면 3-->1 이렇게 신뢰 관계가 간다.
내가 생각하는것의 역방향이라 또 헷갈렸던 부분이었다.

다시 예를 들자면

3,1
1,4
4,5라면

그래프는
5->4->1->3 순으로 신뢰를 하는거다 그러므로
정답 배열의 신뢰도 값은
3 1 4 5
3 2 1 0
이므로 정답은 3번 노드이다.

하지만 신뢰도 값이 같은 노드가 있을 수 있으므로
그 부분도 생각하여 처리하여 주면된다.

코드

#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<sstream>
#include<tuple>
#include<queue>
using namespace std;
static vector<int>Arr[10003];
bool visitied[10003];
int answer[10003];



void BFS(int node);
void revisitied(int num);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		Arr[a].push_back(b);
	}
	for (int i = 0; i <= n; i++)
	{
		revisitied(n);
		BFS(i);
	}
	int maxx =0;
	for (int i = 1; i <= n; i++)
	{
		if (answer[i] > maxx)
		{
			maxx = answer[i];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		if (answer[i] == maxx)
		{
			cout << i << " ";
		}
	}

}
void revisitied(int num)
{
	for (int i = 0; i <= num; i++)
	{
		visitied[i] = false;
	}
}
void BFS(int node)
{
	queue<int>qq;
	qq.push(node);
	visitied[node] = true;
	while (!qq.empty())
	{
		int now = qq.front();
		qq.pop();
		for (int i : Arr[now])
		{
			if (visitied[i] == false)
			{
				visitied[i] =true;
				answer[i]++;
				qq.push(i);
			}
		}
	}

}