Ranking The Cows-G

Algorithm 1

观察题面，可以将 $x > y$ 看做 $x$ 到 $y$ 的一条边，并且当可以排序时的最差情况需要的条件总是就是奶牛数构成的无向完全图的边数，即为 $n(n-1)/2$ 。

这是可以简化为传递闭包，只需要先跑一次 $Floyd$ ，便可以知道当前所知的所有条件的数量，记为 $Cnt$ ,那答案即为 $n(n-1)/2-Cnt$ 。

时间复杂度： $O(n^3)$

期望得分： $60$ 分

#include <bits/stdc++.h>
using namespace std;

int N , M , ToT;

bool Dis[1010][1010];

int main() {
    ios::sync_with_stdio(false);

    cin >> N >> M;
    for(int i = 1 ,x ,y; i <= M; i++) {
        cin >> x >> y;
        Dis[x][y] = true;
    }
    
    for(int k = 1; k <= N; k++) {
        for(int i = 1; i <= N; i++) {
            for(int j = 1; j <= N; j++) {
                Dis[i][j] |= Dis[i][k] & Dis[k][j];
            }
        }
    }

    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            if(Dis[i][j] == true) ToT++;
        }
    }

    cout << N * (N - 1) / 2 - ToT << endl;
    
    return 0;
}

Algorithm 2

根据 $Algorithm 1$ 可知本题只需知道条件的数量，那么其实不用跑一次 $Floyd$ ,多次搜索即可。

时间复杂度： $O(n + m)$

期望得分： $100$ 分

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;

bool book[1010];

vector<int> G[1010];

int N , M , Cnt;


struct Edge {
	int u , v;
};

queue<int> Q;

void BFS(int root) {
	while(!Q.empty()) Q.pop();
	memset(book , 0 , sizeof(book));
	Q.push(root);
	book[root] = true;
 	while(!Q.empty()) {
		int T = Q.front();
        Q.pop();
        for (int i = 0; i < G[T].size(); i++) {
            int v = G[T][i];
            if (book[v] == true) 
				continue;
            book[v] = true;
            Cnt++;
            Q.push(v);
        }
    }
}

int main() {
	ios::sync_with_stdio(false);
	
	for (int i = 1; i <= N; i++) {
        	G[i][i] = true;
    	}
    
    	cin >> N >> M;
    	for (int i = 1 , u , v; i <= M; i++) {
        	cin >> u >> v;
        	G[u].push_back(v);
    	}

    	for (int i = 1; i <= N; i++) {
        	BFS(i);
    	}
    
    	cout << N * (N - 1) / 2 - Cnt << endl;
	
	return 0;
}