https://www.acmicpc.net/problem/17616
17616번: 등수 찾기
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어
www.acmicpc.net
[난이도] 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
'Problem-Solving > BOJ' 카테고리의 다른 글
| [BOJ/백준][Gold3] 12785 : 토쟁이의 등굣길 (C++) (0) | 2021.03.01 |
|---|---|
| [BOJ/백준][Gold3] 1983 : 숫자 박스 (C++) (0) | 2021.03.01 |
| [BOJ/백준][Gold3] 2836 : 수상 택시 (C++) (0) | 2021.03.01 |
| [BOJ/백준][Gold5] 2170 : 선 긋기 (C++) (0) | 2021.03.01 |
| [BOJ/백준][Gold3] 1132 : 합 (C++) (0) | 2021.03.01 |