一个 $O(n^2)$ 的写法莫名奇妙的过了。 思路是先按$x$排序然后模拟建图，如果一个点纵坐标小于当前连通块中最小的纵坐标就直接连上去，否则判断这个点是否能将之前的连通块连起来。
由于第二个操作需要 $O(n)$ 的时间，因此时间复杂度 $O(n^2)$。

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

const int N = 1e5 + 7, inf = 1e9 + 1;

int n, mi[N], cnt, ans;

struct stu{
	int x, y;
} a[N];

bool cmp(stu x, stu y){
	return x.x < y.x;
}

signed main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1, cmp);
	mi[++cnt] = a[1].y, ans = 1;
	for(int i = 2; i <= n; i++){
		if(a[i].y < mi[cnt]){
			if(a[i].x != a[i - 1].x) ans++, mi[++cnt] = a[i].y;
			else mi[cnt] = a[i].y;
		}
		else{
			for(int j = cnt - 1; j > 0; j--){ //cnt是不会减小的，而且我直接遍历的
				if(a[i].y >= mi[j]) ans --, mi[j] = inf;
			}
		}
	}
	printf("%d\n", ans);
	return 0;
}

然后就A了...提交记录

也许这个做法复杂度是正确只是我算错了?但确实比其他解法跑得慢的多。 求大佬解答原因。