[BOJ/백준][Gold4] 14267 : 회사 문화 1 (C++)

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

14267번: 회사 문화 1

 

 

[난이도] Gold4
[유형] DFS

[풀이]
인접리스트를 이용해 칭찬 그래프를 만들고 칭찬을 받은 사람부터 dfs를 시작해
방문하는 모든 부하들에게 칭찬을 더해주면 된다.
이 때, 칭찬의 총 갯수 M마다 dfs를 돌면 시간초과가 나므로 사람 i에 대한 칭찬을 미리 모두 더한 뒤
dfs를 돌려야 한다.

 

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int N,M,ans[100001],s[100001];
vector<int> adj[100001];
void dfs(int n,int k){
    ans[n]+=k;
    for(auto nxt : adj[n]) dfs(nxt,k);
}

int main(){
    scanf("%d%d",&N,&M);
    
    for(int i=1;i<=N;i++){
        int u;
        scanf("%d",&u);
        if(u!=-1) adj[u].push_back(i);
    }
    while(M--){
        int a,w;
        scanf("%d%d",&a,&w);
        s[a]+=w;
    }
    for(int i=2;i<=N;i++){
        if(s[i]>0) dfs(i,s[i]);
    }
    for(int i=1;i<=N;i++) printf("%d ",ans[i]);
}

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