54 lines
1.6 KiB
C++
54 lines
1.6 KiB
C++
#include <bits/stdc++.h>
|
||
|
||
using namespace std;
|
||
|
||
#define N 1001
|
||
|
||
//利用有向图的概念进行模拟，heavy表示谁比谁大的有向图，light表示谁比谁小的有向图
|
||
int heavy[N][N] = {0}, light[N][N] = {0};
|
||
|
||
int main() {
|
||
//n:珍珠的个数
|
||
//m:m组数据
|
||
int n, m, ans = 0;
|
||
//输入+输出重定向
|
||
freopen("../1409.txt", "r", stdin);
|
||
|
||
cin >> n >> m;
|
||
//录入m组数据
|
||
int a, b;
|
||
for (int i = 1; i <= m; i++) {
|
||
cin >> a >> b;
|
||
heavy[a][b] = 1; // a比b 大的话
|
||
light[b][a] = 1; // b比a小
|
||
}
|
||
//Floyd核心算法,引入不同的节点，分别进行探测，直到找到所有节点的关系
|
||
for (int k = 1; k <= n; k++) //k要写在最外层！
|
||
for (int i = 1; i <= n; i++)
|
||
for (int j = 1; j <= n; j++)
|
||
if (i != j && i != k && j != k) {
|
||
if (heavy[i][k] && heavy[k][j]) heavy[i][j] = 1; //如果i比k重且k比j重，那么i比j重
|
||
if (light[i][k] && light[k][j]) light[i][j] = 1; //如果i比k轻且k比j轻，那么i比j轻
|
||
}
|
||
|
||
//输出结果
|
||
for (int i = 1; i <= n; i++) {
|
||
a = 0;
|
||
b = 0;
|
||
for (int j = 1; j <= n; j++) {
|
||
//计算比i大的个数
|
||
if (heavy[i][j])
|
||
a++;
|
||
//计算比i小的个数
|
||
else if (light[i][j])
|
||
b++;
|
||
}
|
||
//如果起过一半的数量，就不是中间节点
|
||
if (a >= (n + 1) / 2 || b >= (n + 1) / 2) ans++;
|
||
}
|
||
cout << ans << endl;
|
||
//关闭文件
|
||
fclose(stdin);
|
||
return 0;
|
||
}
|