[BOJ/백준][Silver1] 1325 : 효율적인 해킹 (C++)

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

1325번: 효율적인 해킹

 

 

[난이도] Silver1
[유형] DFS

[풀이]
dfs를 이용해 각 노드부터 시작해서 방문할 수 있는 총 노드의 개수를 구할 수 있습니다.
이 노드의 개수가 해킹할 수 있는 노드의 개수입니다.

 

#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
int N,M,visit[10001];
vector<int> adj[10001];
map<int,vector<int>> mp;
int dfs(int n){
    visit[n]=1;
    int ret=1;
    for(auto nxt : adj[n]){
        if(!visit[nxt]){
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int u,v;scanf("%d%d",&u,&v);adj[v].push_back(u);
    }
    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        mp[dfs(i)].push_back(i);
    }
    auto [k,res] = *mp.rbegin();
    sort(res.begin(),res.end());
    for(auto a : res) printf("%d ",a);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Silver1/1325.cpp