백준 1325 - 효율적인 해킹

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

 

A가 B를 신뢰한다는 것은 B가 A를 해킹할 수 있다는 뜻이며 B -> A 방향의 엣지가 주어지는 것으로 이해할 수 있다.

 

이 문제는 노드가 최대 10000개이며 우리는 감각적으로 PS를 할 때 1초에 1억 번(최근엔 2~3억) 번의 연산을 할 수 있음을 알고 있다.

 

즉 모든 노드에 대해 일일이 DFS/BFS를 수행하면 노드 한 개가 자기 자신을 포함하여 최대 10000개의 노드를 탐색하므로 $10^{4} \times 10^{4} = 10^{8}$번의 연산을 해야 하고 이는 5초라는 주어진 시간에 걸맞은 풀이가 된다.

 

각 노드마다 BFS혹은 DFS를 이용하여 최대로 해킹 가능한 컴퓨터가 몇 대인지 세주면 된다.

 

이렇게 구한 값은 2차원 선형 자료구조로 관리할 수 있다.

 

C++ 벡터를 예시로 들면 vector<int> ans[컴퓨터를 x대 해킹 가능한 원소들의 집합]으로 표현할 수 있다.

 

이렇게 해킹 가능한 컴퓨터의 숫자가 같은 원소끼리 묶어준 다음 최대로 해킹 가능한 컴퓨터 대수에 소속된 노드를 오름차순으로 출력하면 정답을 받을 수 있다.

 

전체 코드 - DFS

#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#include <bits/stdc++.h>

using namespace std;

int n, m;
int num;
int discovered[10001];
bool finished[10001];
vector<int> graph[10001];
vector<int> ans[10001];

int dfs(int cur, int par)
{
  int ret = 1;
  discovered[cur] = ++num;

  for (int i: graph[cur])
  {
    if (i == par) continue;
    if (discovered[i] == -1) ret += dfs(i, cur);
  }

  finished[cur] = true;
  return ret;
}

void solve()
{
  cin >> n >> m;

  for (int i = 0; i < m; ++i)
  {
    int a, b;
    cin >> a >> b;
    graph[b].push_back(a);
  }

  for (int i = 1; i <= n; ++i)
  {
    sort(graph[i].begin(), graph[i].end());
    graph[i].erase(unique(graph[i].begin(), graph[i].end()), graph[i].end());
  }

  for (int i = 1; i <= n; ++i)
  {
    num = 0;
    memset(finished, 0, sizeof finished);
    memset(discovered, -1, sizeof discovered);
    ans[dfs(i, -1)].push_back(i);
  }

  for (int i = 10000; i >= 1; --i)
  {
    if (ans[i].size())
    {
      sort(ans[i].begin(), ans[i].end());
      for (int j: ans[i]) cout << j << ' ';
      return;
    }
  }
}

int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);

  solve();
}