Algorithm/BOJ
등수 찾기 - 17616
jhg0406
2020. 7. 19. 20:51
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
|
//17616 - 등수 찾기
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int N, M, X;
vector<vector<int>> uadj;
vector<vector<int>> dadj;
int U, V;
void init() {
cin >> N >> M >> X;
dadj = uadj = vector<vector<int>>(N+1);
int u, v;
for(int i = 0; i<M; ++i) {
cin >> u >> v;
uadj[v].push_back(u);
dadj[u].push_back(v);
}
}
int bfs(vector<vector<int>>& adj) {
vector<int> level(N+1, -1);
level[X] = 0;
int ret = 0;
queue<int> Q;
Q.push(X);
while(!Q.empty()) {
int here = Q.front();
Q.pop();
for(int i = 0; i<adj[here].size(); ++i) {
int there = adj[here][i];
if(level[there] == -1) {
++ret;
Q.push(there);
level[there] = level[here] + 1;
}
}
}
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
init();
U = bfs(uadj) + 1;
V = N - bfs(dadj);
cout << U << " " << V;
}
|
cs |
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
등수 찾기
주어지는 정보로 그래프 2개를 만들어 줍니다.(하나는 간선의 방향이 상위랭크를 향하게, 다른 하나는 하위 랭크를 향하게)
그리고 X에서부터 두개의 그래프 각각 bfs를 사용해서 위나 밑에 몇개의 정점이 있는지 count해주면 X보다 위나 밑에 확실히 있는 점들의 개수를 알 수 있습니다.
