1325. 효율적인 해킹

 

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

1325번: 효율적인 해킹

 

dfs로 풀었다... 

중간에 해맸는데 어찌저찌 다른 분들의 풀이를 참고를 했던 것 같다. 

내가 도달한 것은 그래프 연결을 a->b에서 b를 해킹하면 a도 해킹된다는 거니 b -> a로만 연결시켜주는 것이었다. 

나머진 최대 해킹 수를 구하는 것을 생각 못해서 참조했던거같다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <cmath>
using namespace std;

#define MAX 10001

vector<int> arr[MAX];
bool visited[MAX];
int check;
int maxHack;
vector<pair<int, int>> ans; 

void dfs(int x)
{
	visited[x] = true;
	
	for (int i = 0; i < arr[x].size(); i++)
	{
		int next = arr[x][i];
		if (visited[next] == false)
		{
			check++; 
			dfs(next);
		}
	}
}

int main() {

	int n, m; 
	cin >>n >> m;

	for (int i = 0; i < m; i++) {

		int a, b ;
		cin >> a >> b;
		//arr[a].push_back(b);
		arr[b].push_back(a);
	}

	for (int i = 1; i <= n; i++)
	{
		memset(visited, false, sizeof(visited));
	
		if (visited[i] == false)
		{
			check = 0; 
			dfs(i);
			if (check > 0)
			{
				if (check > maxHack)
					maxHack = check;
			}
			ans.push_back({ i, check });
		}
		
	}

	for (int i = 0; i < ans.size(); i++)
	{
		if(maxHack == ans[i].second)
			cout << ans[i].first << " ";
	}

    return 0;
}