728x90
2458번: 키 순서
1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여
www.acmicpc.net
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
bool dp[501][501];
int main() {
int n, m;
cin >> n;
cin >> m;
int a, b;
for (int i = 0; i < m; i++) {
cin >> a;
cin >> b;
dp[a][b] = true;
}
int count = 0;
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dp[i][k] == true && dp[k][j] == true)
{
dp[i][j] = true;
// count++;
}
}
}
}
for (int i = 1; i <= n; i++) {
bool toggle = false;
for (int j = 1; j <= n; j++) {
if (i != j) {
if (dp[i][j] == false && dp[j][i]==false) { // true가 하나라도 있으면 관계성립 가능
toggle = true;
break;
}
}
}
if (toggle == false) { count++; }
}
cout << count << endl;
}spacefordeveloper.tistory.com/197
순위 - 플로이드 와샬
플로이드 와샬 알고리즘으로 푸는 문제입니다. 다익스트라 알고리즘의 경우에는 하나의 정점에서 출발했을 때 다른 모든 정점으로의 최단 경로를 구하는 것입니다. 참고: spacefordeveloper.tistory.com
spacefordeveloper.tistory.com
이 문제와 비교해보기
'백준 > 그래프' 카테고리의 다른 글
| 최단경로 -1753번 (0) | 2021.08.25 |
|---|---|
| 이진검색트리 - 5639번 (java) (0) | 2021.08.11 |
| 트리의 부모찾기 (0) | 2021.04.26 |
