[BOJ/백준][Gold3] 17616 : 등수 찾기 (C++)

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

17616번: 등수 찾기

 

 

[난이도] Gold3
[유형] DFS

[풀이]
정방향,반대방향 인접 리스트를 이용해서 dfs를 두번하면 최대,최저 등수를 구할 수 있다.

 

#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
vector<int> adj[2][100001];
bool visit[100001];
int N,M,X,k;
int dfs(int n){
    visit[n]=1;
    int ret=1;
    for(auto v : adj[k][n]){
        if(!visit[v]) ret+=dfs(v);
    }
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&X);
    for(int i=0;i<M;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        adj[0][u].push_back(v);
        adj[1][v].push_back(u);
    }
    int U,V;
    U=N-dfs(X)+1;
    k=1;
    V=dfs(X);
    printf("%d %d",V,U);
}

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