백준 1325번: 효율적인 해킹

문제링크: https://www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

전형적인 DFS문제 어렵지 않다.
사실 정답률  보고, 얼마나 오래 걸릴까 걱정했는데 1시간? 30분? 이렇게 푼 것 같다.

그러나 문제를 착각할 수가 있다.
A가 B를 신뢰한다 == 서로가 서로를 신뢰하다고 보면 안된다.

그래서 벡터에 넣어놓고 보면 방향성이 있는 그래프로 확인할 수 있다.

 

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

vector<int> v[10001];
bool bVisited[10001];
int nHackingCount[10001] = { 0, };

int N, M;

void DFS(int nStart)
{
	nHackingCount[nStart]++;
	
	for (int i = 0; i < v[nStart].size(); i++)
	{
		int nNextStart = v[nStart][i];
		if (false == bVisited[nNextStart])
		{
			bVisited[nNextStart] = true;
			DFS(nNextStart);
		}
	}
}
int main(void)
{
	cin >> N >> M;
	int nComputer1, nComputer2;

	for (int i = 0; i < M; i++)
	{
		cin >> nComputer1 >> nComputer2;
		v[nComputer1].push_back(nComputer2);
	}

	for (int i = 1; i <= N; i++)
	{
		memset(bVisited, false, sizeof(bVisited));
		bVisited[i] = true;
		DFS(i);
	}

	int nTempMax = 0;

	for (int i = 1; i <= N; i++)
	{
		nTempMax = max(nTempMax, nHackingCount[i]);
	}

	for (int i = 1; i <= N; i++)
	{
		if (nTempMax == nHackingCount[i])
		{
			printf("%d ",i);
		}
	}
	cout << endl;

	return 0;
}