[BOJ/백준][Gold4] 2458 : 키 순서 (C++)

www.acmicpc.net/problem/2458

2458번: 키 순서

 

[난이도] Gold4

[유형] DFS

 

[풀이]

in,out 배열을 만들고 각 점에서 DFS를 해서 방문할 수 있는 점의 개수를
out에, DFS중 어떤 점을 방문할때 그 점의 in값을 1씩 증가 시킨다.
in[i]+out[i]==N인 점이 정답인 점들이다.

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
int N,M,in[501],out[501],ans;
vector<int> adj[501];
bool visit[501];
int dfs(int n){
    visit[n] = 1;
    int ret = 1;
    for(int nxt : adj[n]){
        if(!visit[nxt]){
            in[nxt]++;
            ret+=dfs(nxt);
        }
    }
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<M;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        adj[a].push_back(b);
    }

    for(int i=1;i<=N;i++){
        memset(visit,0,sizeof(visit));
        out[i] = dfs(i);
    }
    for(int i=1;i<=N;i++) if(in[i]+out[i]==N) ans++;
    printf("%d",ans);
}

 

github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2458.cpp