백준 1325번 효율적인 해킹 ( C++ )

문제

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

1325번: 효율적인 해킹

 

해설

dfs/bfs둘가 구현가능한 문제

실수만 안하면 어렵지 않은 문제

코드

#include <bits/stdc++.h>
using namespace std;
int n, m, mn, visited[10004], tmp, a, b;
vector<int> v[10004];
vector<int> ret;
int dfs(int c)
{
  visited[c] = 1;
  int cnt = 1;
  for (int i : v[c])
  {
    if (!visited[i])
      cnt += dfs(i);
  }
  return cnt;
}
 
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin >> n >> m;
  for (int i = 0; i < m; i++)
  {
    cin >> a >> b;
    v[b].push_back(a);
  }
 
  for (int i = 1; i <= n; i++)
  {
    fill(&visited[0], &visited[0] + 10004, 0);
    tmp = dfs(i);
    if (tmp > mn)
    {
      mn = tmp;
      ret.clear();
      ret.push_back(i);
    }
    else if (tmp == mn)
    {
      mn = tmp;
      ret.push_back(i);
    }
  }
  for (int i : ret)
    cout << i << " ";
}