//本题首先的困难在于要明白如果想知道一个序列的排序序列再不考虑传递影响的情况下需要有n(n-1)/2个大小关系。 //本题给出的大小关系里面有受传递影响可以推导出的一些大小关系,比如:2>1,1>4得到2>4; //那么将其扩展到n(n-1)/2里面的所有关系,也就是说需要求出间接得到的所有大小关系。 //那么在这时候可以联想到图论里面的弗洛伊德算法。将其每个点都作为中转点一次,然后就可以动态规划的求出间接得到的大小关系。 /*#include <bits/stdc++.h> using namespace std; const int maxn = 1000+10; int n, m; int a[maxn][maxn]; int main() { int x, y; cin>>n>>m; for (int i=1;i<=m;i++) { cin>>x>>y; a[x][y] = 1; } for (int k=1;k<=n;k++) { for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (a[i][k]&&a[k][j]) { a[i][j] = 1; } } } } int cnt = 0; for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (!a[i][j]&&!a[j][i]) { cnt++; } } } cout<<(cnt-n)/2; return 0; }*/ //至于二进制优化,本题对于两个点之间的关系就大于小于。如果我们只考虑大于就可以得到有哪些点是已知的。 //其实循环和弗洛伊德算法是一致的将i当中中转的点。只不过得知中转点可以中转之后所有与之有关系的点都可以使用按位或运算直接求罢了。 //最后得到哪些点是已知的那完全的数量减去就行。 #include <bits/stdc++.h> using namespace std; bitset<1001> bt[1001]; int n, m; int main() { int x, y; cin>>n>>m; for (int i=1;i<=m;i++) { cin>>x>>y; bt[x][y] = 1; } for (int i=1;i<=n;i++) { for (int j=1;j<=n;j++) { if (bt[j][i]) bt[j] |= bt[i]; } } int ans = (n-1)*n/2; for (int i=1;i<=n;i++) { ans -= bt[i].count(); } cout<<ans<<endl; return 0; }