[BOJ | 백준] 1325번: 효율적인 해킹

출처: www.acmicpc.net/problem/1325

1325번: 효율적인 해킹

각 노드에서 탐색을 수행해 접근가능한 노드의 수를 계산해 해결할 수 있다.

#include<iostream>
#include<vector>
#include<queue>
using namespace std;

int cnt_children[10001];
vector<int> graph[10001];
queue<int> dfs_queue;
vector<bool> visited;
int N,M,parent,child,max_value,current,cnt;

void bfs(int n){
  visited.resize(N+1);
  dfs_queue.push(n);
  visited[n]=true;
  cnt=0;
  while(!dfs_queue.empty()){
    current=dfs_queue.front();
    dfs_queue.pop();
    cnt++;
    for(int i=0;i<graph[current].size();i++){
      if(visited[graph[current][i]]) continue;
      dfs_queue.push(graph[current][i]);
      visited[graph[current][i]]=true;
    }
  }
  cnt_children[n]=cnt;
  visited.clear();
}

int main(){
  max_value=0;
  cin>>N>>M;
  while(M--){
    cin>>child>>parent;
    graph[parent].push_back(child);
  }
  for(int n=1;n<=N;n++){
    bfs(n);
    if(max_value<cnt_children[n]) max_value=cnt_children[n];
  }
  for(int n=1;n<=N;n++){
    if(cnt_children[n]==max_value)  cout<<n<<" ";
  }
}