题意：有n个人，每个人在2个oj（cc， tg）上分别都有一个ranting，每个oj上面的ranting都不一样，当且仅当存在一个序列 P0, P1, . . . , Pk 使得对于每一个Pi来说， Pi有1个或者2个oj的ranting大于Pi+1，表示P0可以打败Pk
思路：好好理解一下题意，其实先不看tg， 先按cc从小到大排序后，后面的人可以打败他前面所有的人， 同理，按tg排序的时候，后面的人也能打败他前面所有人，所以，第一次按cc排序后，每个点和它前面的点建单项边，如果可以到达，则表示可以打败，第二次再按tg排序，同样的方式建边，然后dfs搜一次，搜索的时候，需要理解的地方是vis[]标记是不需要清空的，这样才能保证时间复杂度，还有一个是计数的s变量是不需要每次初始化的，这里要理解到，后面的人一定能打败前面的人，而前面的人能打败的，后面的一样可以打败，比如 A打败B C打败A， 那么C一定也可以打败B，注意这里，在当前的排序下面，B不一定在C的前面，可能在C的后面，理解了这里基本上就没有问题了
AC代码：
#include "iostream" #include "iomanip" #include "string.h" #include "stack" #include "queue" #include "string" #include "vector" #include "set" #include "map" #include "algorithm" #include "stdio.h" #include "math.h" #pragma comment(linker, "/STACK:102400000,102400000") #define bug(x) cout<<x<<" "<<"UUUUU"<<endl; #define mem(a,x) memset(a,x,sizeof(a)) #define step(x) fixed<< setprecision(x)<< #define mp(x,y) make_pair(x,y) #define pb(x) push_back(x) #define ll long long #define endl (" ") #define ft first #define sd second #define lrt (rt<<1) #define rrt (rt<<1|1) using namespace std; const ll mod=1e9+7; const ll INF = 1e18+1LL; const int inf = 1e9+1e8; const double PI=acos(-1.0); const double eps=1e-9; const int N=1e5+100; struct Node{ int cc, tf, id; }p[N]; bool cmp_cc(Node a, Node b){ return a.cc<b.cc; } bool cmp_tf(Node a, Node b){ return a.tf<b.tf; } vector<int> G[N]; int ans[N],vis[N],sum; void dfs(int u){ if(vis[u]) return; sum++; vis[u]=1; for(auto v : G[u]){ dfs(v); } } int main(){ freopen("codecoder.in","r",stdin); freopen("codecoder.out","w",stdout); int n; scanf("%d",&n); for(int i=0; i<n; ++i){ scanf("%d %d", &p[i].cc, &p[i].tf); p[i].id=i; } sort(p,p+n,cmp_cc); for(int i=1; i<n; ++i){ G[p[i].id].pb(p[i-1].id); } sort(p,p+n,cmp_tf); for(int i=1; i<n; ++i){ G[p[i].id].pb(p[i-1].id); } for(int i=0; i<n; ++i){ dfs(p[i].id); ans[p[i].id]=sum-1; } for(int i=0; i<n; ++i) printf("%d ",ans[i]); return 0; }