[알고리즘] 백준 1325

백준 1325번 효울적인 해킹

해결 과정 요약

노드간 간선을 저장하고 dfs를 해준다. dfs 호출 횟수를 map에 저장한다.
이 map의 key는 int, value는 std::vector 이다.
key에는 cnt(해킹가능한 컴퓨터 수), value에는 컴퓨터 번호를 담는다.
map은 자동으로 정렬이 되므로 map.rbegin()을 이용해 해킹가능한 컴퓨터 수가 가장 큰 vector를 뽑아낸다.
vector는 오름차순으로 푸시했으니 단순히 vector의 모든 값을 출력하면 정답이다.

풀이

#include <bits/stdc++.h>
using namespace std;

int N,M,A,B,cnt;
vector<int> com[10004];
int visited[10004];
map<int,vector<int>> hack;

void dfs(int n){
    cnt++;
    visited[n] = 1;
    for(int i=0; i<com[n].size(); i++){
        if(visited[com[n][i]] == 0){
            dfs(com[n][i]);
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N >> M;
    for(int i=0; i<M; i++){
        cin >> A >> B;
        com[B].push_back(A);
    }
    for(int i=1; i<=N; i++){
        cnt = 0; fill(visited, visited + 10004, 0);
        dfs(i);
        hack[cnt].push_back(i);
    }
    auto e = hack.rbegin();
    for(int i=0; i<e->second.size(); i++){
        cout << e->second[i] << " ";
    }
    
    return 0;
}

코멘트

그래프의 간선을 저장하는 법을 아는지 묻는 문제