https://www.acmicpc.net/problem/2458
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자.
학생들의 키를 비교한 결과가 주어질 때, 자신의 키가 몇 번째인지 알 수 있는 학생들이 모두 몇 명인지 계산하여 출력하는 프로그램을 작성하시오.
첫째 줄에 학생들의 수 N (2 ≤ N ≤ 500)과 두 학생 키를 비교한 횟수 M (0 ≤ M ≤ N(N-1)/2)이 주어진다. 다음 M개의 각 줄에는 두 학생의 키를 비교한 결과를 나타내는 두 양의 정수 a와 b가 주어진다. 이는 번호가 a인 학생이 번호가 b인 학생보다 키가 작은 것을 의미한다.
자신이 키가 몇 번째인지 알 수 있는 학생이 모두 몇 명인지를 출력한다.
풀었던 문제를 다시 풀어보았다
문제에서 자신의 키가 몇번째인지 알 수 있는 학생의 수를 구하라고 그랬는데 이는 자기 자신을 제외한 나머지 학생들이 모두 연결되어 있으면 키의 순서를 정확하게 파악 가능하기 때문이다.
이럴 경우는 답을 1증가시켜줘서 문제를 해결한다.
나머지는 주석을 참고!
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 501
#define INF 1e9
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
int dist[MAX][MAX];
void resetGraph(){
for(int i = 1; i < MAX; i++){
for(int j = 1; j < MAX; j++){
dist[i][j] = INF;
}
}
}
void floyd(int n){
for(int k = 1; k <= n; k++){ // k : 거쳐가는 정점
for(int i = 1; i <= n; i++){ // i : 행(출발 정점)
for(int j = 1; j <= n; j++){ // j : 열(도착 정점)
// 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
int main(){
fastio;
int n,m;
cin >> n >> m;
resetGraph();
for(int i = 0; i < m; i++){
int a,b; cin >> a >> b;
dist[a][b] = 1;
}
floyd(n);
int ans = 0; // 정답
for(int i = 1; i <= n; i++){
int cnt = 0;
for(int j = 1; j <= n; j++){
if(dist[i][j] != INF || dist[j][i] != INF){ // 키가 작은 사람을 알거나 또는 키가 큰 사람을 알면
cnt++;
}
}
if(cnt == n - 1) ans++; // 자기 자신을 제외한 모든 사람과 연결되어 있으면
}
cout << ans;
return 0;
}