# Description

Each of Farmer John's N cows (1 ≤ N ≤ 1,000) produces milk at a different positive rate, and FJ would like to order his cows according to these rates from the fastest milk producer to the slowest.

FJ has already compared the milk output rate for M (1 ≤ M ≤ 10,000) pairs of cows. He wants to make a list of C additional pairs of cows such that, if he now compares those C pairs, he will definitely be able to deduce the correct ordering of all N cows. Please help him determine the minimum value of C for which such a list is possible.

John已经比较了M对奶牛的产奶率。他想列一个清单，如果他比较了C对奶牛，他就能推测出所有奶牛N的顺序。你需要帮助John算出最小对数C。

Input

Line 1: Two space-separated integers: N and M Lines 2..M+1: Two space-separated integers, respectively: X and Y. Both X and Y are in the range 1...N and describe a comparison where cow X was ranked higher than cow Y.

Output

Line 1: A single integer that is the minimum value of C.

Sample Input

`5 5 2 1 1 5 2 3 1 4 3 4`

Sample Output

`3`

Hint

From the information in the 5 test results, Farmer John knows that since cow 2 > cow 1 > cow 5 and cow 2 > cow 3 > cow 4, cow 2 has the highest rank. However, he needs to know whether cow 1 > cow 3 to determine the cow with the second highest rank. Also, he will need one more question to determine the ordering between cow 4 and cow 5. After that, he will need to know if cow 5 > cow 3 if cow 1 has higher rank than cow 3. He will have to ask three questions in order to be sure he has the rankings: "Is cow 1 > cow 3? Is cow 4 > cow 5? Is cow 5 > cow 3?"

```#include<cstdio>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;

int n,m,ans;
bool mp[1005][1005];
vector<int>ru[1005],chu[1005];

int main()
{
scanf("%d%d",&n,&m);

for (int i = 0; i < m; i++)
{
int a,b;
scanf("%d%d", &a, &b);
ru[b].push_back(a);
chu[a].push_back(b);
mp[a][b] = true;
}

for (int k = 1; k <= n; k++)
for (int a = 0; a < ru[k].size(); a++)
for (int b = 0; b < chu[k].size(); b++)
{//C++11的“int i:ru[k]”POJ貌似编译不过去
int i = ru[k][a];
int j = chu[k][b];
if(!mp[i][j])
{
ru[j].push_back(i);
chu[i].push_back(j);
mp[i][j] = true;
ans++;
}
}

printf("%d\n",(n-1)*n/2-m-ans);

return 0;
}```

```#include<cstdio>
#include<bitset>
#include<iostream>
using namespace std;

const int maxn=1000+5;
int n,m,ans;
bitset<maxn>bit[maxn];//类似于上面那个方法的mp二维数组

int main()
{
scanf("%d%d",&n,&m);

for (int i = 0; i < m; i++)
{
int a,b;
scanf("%d%d",&a,&b);
bit[a].set(b);//将bit[a][b]设为1
}

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (bit[j][i])//这其实就是个暴力的Floyd
bit[j] |= bit[i];//或运算使得i中为1的点（即有向图中i指向的点），j也指向它

for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (bit[i][j])
ans++;
//这里的ans是枚举之后得到的所有边，已经Floyd处理过了，所以包括隐藏的

cout << n*(n-1)/2-ans << endl;

return 0;
}```

203 篇文章31 人订阅

0 条评论

## 相关文章

1.6K8

1032

732

### 排序一栏（总结帖）

学了很多的排序，基数排序，堆排序，希尔排序，选择排序，归并排序，快速排序，冒泡排序.....等等，尽管网上好文，如堆山之牛毛，但是还是没有自己写，来...

2103

1052

42610

1342

2726

1791

2208